Check For Dead End In A BST

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
15 upvotes
Asked in company
Codenation

Problem statement

You are given a Binary Search Tree (BST) that contains positive integers only. Your task is to find out whether the BST contains a Dead End. A BST is said to have a Dead End if there exists a leaf node in the BST, for which it is impossible to insert any further nodes after that node in that BST. If such nodes do not exist, then the BST doesn’t contain a Dead End.

A binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree whose internal nodes each store a value greater than all the values in the node's left subtree and less than those in its right subtree.

Follow Up : 
Can you solve this in O(N) time, and O(H)  space complexity?
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

Then the T test cases follow. 

The first and only line of each test case contains elements in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take -1 in its place.

For example, the input for the tree depicted in the below image would be :

bst_example 

4
2 6
1 3 5 7
-1 -1 -1 -1 -1 -1 -1 -1

Explanation :

Level 1 :
The root node of the tree is 4

Level 2 :
Left child of 4 = 2
Right child of 4 = 6

Level 3 :
Left child of 2 = 1
Right child of 2 = 3
Left child of 6 = 5
Right child of 6 = 7

Level 4 :
Left child of 1 = null (-1)
Right child of 1 = null (-1)
Left child of 3 = null (-1)
Right child of 3 = null (-1)
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 7 = null (-1)
Right child of 7 = null (-1)

The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).
Note : 
The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:

4 2 6 1 3 5 7 -1 -1 -1 -1 -1 -1 -1 -1
Output format : 
For each test case, print True or False in a separate line.

Output for each test case will be printed in a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 100
1 <= N <= 5000
1 <= node data <= 10^9, (where node data != -1)
Where N denotes the number of nodes in the given tree.

Time Limit: 1 second
Sample Input 1 :
2
10 6 12 2 8 11 15 -1 -1 -1 -1 -1 -1 -1 -1
7 4 8 -1 -1 -1 -1
Sample Output 1 :
True
False
Explanation for sample 1 :
For the first test case, the given BST is depicted below.

bst_input1

So, it is impossible to insert any node after the node having the data 11.

For the second test case, the given BST is depicted below.

bst_input1_ex2

New nodes can be inserted after both the leaf nodes.
Sample Input 2 :
2
5 3 7 -1 -1 6 8 -1 -1 -1 -1
2 1 -1 -1 -1
Sample output 2 :
True
True
Hint

Think of a brute force solution to check whether there exists a leaf node for which it is impossible to insert any further nodes.

Approaches (3)
Brute-force

Note that a leaf node having a value val is said to Dead End if nodes having values (val + 1) and (val - 1) already exist in the tree. However, for a leaf node having the value 1, we will call it a Dead End, if the node having value 2 is present in the BST, as the BST can’t contain the value 0. So, we will traverse the BST and for each leaf node, we will write another search function to search whether the nodes having the value (val + 1) and (val - 1) exist in the BST. If both of these nodes exist for any of the leaf nodes, then we return true, otherwise, we return false.

 

Steps :

 

  1. If root == NULL, then return false.
  2. Create an empty Queue q to traverse the BST in level order traversal. Push the root to the queue. However, it is perfectly fine to choose any other traversal methods.
  3. While q is not empty, do:
    1. Create a node to store the first node from the queue, i.e. curr = q.front.
    2. Pop the first node, i.e. q.pop.
    3. If curr.left == NULL and curr.right == NULL, do:
      1. Implement a function to search for the nodes having value curr.data + 1 and curr.data - 1. But we should handle the node having the value 1 separately.
      2. So, if curr.data = 1, then if search(root, 2) returns true, then we return true. Else, if both the search(root, curr.data+1) and search(root, curr.data-1) return true, then we return true.
    4. Else, push the children of the curr node to the queue.
  4. Finally, when the queue is empty, that means we have traversed the whole BST and there are no Dead Ends in the BST. Hence, we return false.

 

search(Node *root, int val):

 

  1. If root == NULL, then return false.
  2. If root.data == val, then return true.
  3. If root.data > val, then return search(root.left, val).
  4. Else, return search(root.right, val).
Time Complexity

O(N*H), where N is the number of nodes, and  H is the height of the given BST(Binary Search Tree).

 

In the worst case, for a complete tree, the number of leaf nodes is in the order of N, and for each node, we are searching in a given BST which can take O(H) time. Hence, the overall time complexity will be O(N*H).

Space Complexity

O(N), where N is the total number of nodes in the given BST.

 

In the worst case, almost all the nodes of the tree will be pushed into the queue. Hence, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Check For Dead End In A BST
Full screen
Console