Last Updated: 12 Feb, 2021

Check For Dead End In A BST

Moderate

Asked in company

Solve now

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?

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

Solve now

Approaches

01 Approach

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 :

If root == NULL, then return false.
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.
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.
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):

If root == NULL, then return false.
If root.data == val, then return true.
If root.data > val, then return search(root.left, val).
Else, return search(root.right, val).

Solve now

02 Approach

So, instead of searching the BST again for all the leaf nodes, we can store the values of the nodes in a HashSet first. Then traverse the BST again and for each leaf node, check whether the nodes with data (val + 1) and (val - 1) are present in the HashSet or not.

Steps :

If root == NULL, then return false.
Create two HashSets called all and leaves. The all set stores all the nodes in the BST and the leaves set stores the leaf nodes only.
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.
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. Insert curr.data into the all set.
4. If curr.left == NULL and curr.right == NULL, do:
  1. Insert curr.data into the leaves set.
5. Else, push the children of the curr node to the queue.
Now, traverse all the nodes in the leaves set and do:
1. If data = 1 and the data 2 is present in all set, then we return true.
2. Else, if data + 1 and data - 1 is present in the all set, then return true.
Finally, return false.

Solve now

03 Approach

Here, the idea is to store a range of minimum and maximum values for each node in the BST. So, we will initialize the minimum to 1 and maximum to INT_MAX for the root node. Then, traverse the BST, and if maximum = minimum for any of the leaf nodes, then return true. Call the function recursively for the left child by updating the maximum value to min(root.data-1, maximum) and for the right child by updating the minimum value to max(root.data+1, minimum).

Steps :

If root == NULL, then return false.
Create two variables minimum and maximum and initialize them to 1 and INT_MAX respectively.
Call the recursive function isDeadEndUtil(root, minimum, maximum) and return it.

isDeadEndUtil(Node *root, int minimum, int maximum):

If root == NULL, then return false.
If root.left == NULL and root.right == NULL, then:
1. If minimum == maximum, then return true.
2. Else, return false.
Call the function recursively for the left child and right child by updating the maximum and minimum respectively, and return true, if either of them returns true, i.e. return isDeadEndUtil(root.left, minimum, max(root.data-1, maximum)) || isDeadEndUtil(root.right, max(root.data+1, minimum), maximum).

Solve now