Binary Search Trees: Check if the BST has a dead end

Problem Statement:

You are given a root node of a BST. You need to check if it has a dead end or not.

A dead end is a node, where you will not be able to insert any other nodes after it.

BST should contain +ve integers only.

Example

               8
             /   \ 
           5      9
         /   \
        2     7
       /
      1  

Yes. In the node “1”, is a dead end, because you cannot insert any element.

Solution

In the solution we need to check if for the leaf node with a value “x”, “x+1” and “x-1” present in BST.

With a leaf node of value 1, we cannot check for 0 as BST should have only +ve integers.

We store all the leaves value in separate hash and we check for every leaf, “x+1” and “x-1” are present or not.

Solution in C++

#include<iostream>
#include<vector>
#include<string>
#include<unordered_set>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};

Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* insert_into_bst(Node* node, int data) 
{ 
    if (node == NULL) return get_new_node(data); 
  
    if (data < node->data) 
        node->left  = insert_into_bst(node->left, data); 
    else if (data > node->data) 
        node->right = insert_into_bst(node->right, data);    
  
    return node; 
} 

void print_inorder(Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 

void insert_into_hash(Node * root, unordered_set<int> &all_nodes,
                          unordered_set<int> &leaf_nodes)
{
    if (root == NULL)
        return ;
 
    all_nodes.insert(root->data);
 
    if (root->left==NULL && root->right==NULL)
    {
        leaf_nodes.insert(root->data);
        return ;
    }
 
    insert_into_hash(root-> left, all_nodes, leaf_nodes);
    insert_into_hash(root->right, all_nodes, leaf_nodes);
}
 

bool check_is_dead_end(Node *root)
{
    // Base case
    if (root == NULL)
        return false ;
 

    unordered_set<int> all_nodes, leaf_nodes;
 
    all_nodes.insert(0);
 
    insert_into_hash(root, all_nodes, leaf_nodes);
 
    for (auto i = leaf_nodes.begin() ; i != leaf_nodes.end(); i++)
    {
        int x = (*i);
 
        if (all_nodes.find(x+1) != all_nodes.end() &&
            all_nodes.find(x-1) != all_nodes.end())
            return true;
    }
 
    return false ;
}
int main()
{
    Node *root_1 = NULL; 
    root_1 = insert_into_bst(root_1, 1); 
    insert_into_bst(root_1, 2); 
    insert_into_bst(root_1, 3); 
    insert_into_bst(root_1, 4); 
    insert_into_bst(root_1, 5); 

    if (check_is_dead_end(root_1) == true)
        cout << "Yes, BST has a dead end " << endl;
    else
        cout << "No, BST does not has a dead end " << endl;
    return 0;
}

Output:

No, BST does not has a dead end