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