Problem Statement

Given a Binary search Tree that contains positive integer values greater then 0. The task is to complete the function isDeadEnd which returns true if the BST contains a dead end else returns false. Here Dead End means, we are not able to insert any element after that node.

Examples:

Input :
               8
             /   \\
           5      9
         /  \\
        2    7
       /
      1

Output : Yes
Explanation : Node "1" is the dead End because after that
              we cant insert any element.

Input :
              8
            /   \\
           7     10
         /      /   \\
        2      9     13

Output : Yes
Explanation : We can't insert any element at
              node 9.

**Input:**The first line of the input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow. Each test case consists of three lines. First line of each test case contains an integer N denoting the no of nodes of the BST . Second line of each test case consists of 'N' space separated integers denoting the elements of the BST. These elements are inserted into BST in the given order.

**Output:**The output for each test case will be 1 if the BST contains a dead end else 0.

**Constraints:**1<=T<=1001<=N<=200

Problem Link

Check whether BST contains Dead End or not - GeeksforGeeks

Approach

If we take a closer look at the problem, we can notice that we basically need to check if there is a leaf node with value x such that x+1 and x-1 exist in BST with the exception of x = 1. For x = 1, we can’t insert 0 as the problem statement says BST contains positive integers only.

To implement the above idea we first traverse the whole BST and store all nodes in a hash_map. We also store all leaves in a separate hash to avoid re-traversal of BST. Finally, we check for every leaf node x, if x-1 and x+1 are present in hash_map or not.

Code

/*You are required to complete below method */
unordered_set<int> nodes;// to keep track of visited nodes
unordered_set<int> leaves;// to keeptrack of visited leaves

void preorder(Node *root)
{
    if(!root)
    return;
    
    nodes.insert(root->data);
    if(!root->left&&!root->right)
    leaves.insert(root->data);
    
    preorder(root->left);
    preorder(root->right);
}
bool isDeadEnd(Node *root)
{
    nodes.clear();
    leaves.clear();
    
    if(!root)
    return false;
    
    preorder(root);
    
    for(int x:leaves)
    {
        if(x!=1)
        {
            if(nodes.find(x+1)!=nodes.end()&&nodes.find(x-1)!=nodes.end())
            return true;
        }
        else if(x==1)
        {
            if(nodes.find(x+1)!=nodes.end())
            return true;
        }
    }
    
    return false;
    
}