Given a Binary Search Tree that contains positive integer values greater than 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 integer element after that node.
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.
We have discussed a solution in below post.
The idea in this post is based on method 3 of Check if a binary tree is BST or not.
First of all, it is given that it is a BST and nodes are greater than zero, root node can be in the range [1, ∞] and if root val is say, val, then left sub-tree can have the value in the range [1, val-1] and right sub-tree the value in range [val+1, ∞].
we need to traverse recursively and when the the min and max value of range coincided it means that we cannot add any node further in the tree.
Hence we encounter a dead end.
Following is the simple recursive solution to the problem.
# Python 3 Program to check if there
# is a dead end in BST or not.
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# A utility function to insert a
# new Node with given key in BST
def insert(node, key):
# If the tree is empty,
# return a new Node
if node == None:
# Otherwise, recur down the tree
if key < node.data: node.left = insert(node.left, key) elif key > node.data:
node.right = insert(node.right, key)
# return the (unchanged) Node pointer
# Returns true if tree with given
# root contains dead end or not.
# min and max indicate range
# of allowed values for current node.
# Initially these values are full range.
def deadEnd(root, Min, Max):
# if the root is null or the recursion
# moves after leaf node it will return
# false i.e no dead end.
if root == None:
# if this occurs means dead
# end is present.
if Min == Max:
# heart of the recursion lies here.
return (deadEnd(root.left, Min, root.data – 1) or
deadEnd(root.right, root.data + 1, Max))
# Driver Code
if __name__ == ‘__main__’:
# 5 11
# 2 7
root = None
root = insert(root, 8)
root = insert(root, 5)
root = insert(root, 2)
root = insert(root, 3)
root = insert(root, 7)
root = insert(root, 11)
root = insert(root, 4)
if deadEnd(root, 1, 9999999999) == True:
# This code is contributed by PranchalK