Given a Binary search Tree that contains positive integer values greater then 0. The task is to check whether the BST contains a dead end or not. 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.
class Solution {
public boolean bstDeadEnd(Node node, int min, int max) {
if (node == null)
return false;
if (node.data == min && node.data == max)
return true;
return bstDeadEnd(node.left, min, node.data - 1) || bstDeadEnd(node.right, node.data + 1, max);
}
public boolean deadEnd(Node node) {
// As the given BST can only have positive Integers
return bstDeadEnd(node, 1, Integer.MAX_VALUE);
}
}