Python Program to find the dead end in a Binary Search Tree(BST)
This program creates a Binary Search Tree as follows by inserting a node in such a way
that the data value of the left node of every sub-tree is less than the root of that
node and the data value of the right node of that sub-tree is greater than its root.
Here is the Binary Search Tree used in this program:
/ \ \
1 4 10
If you look at the tree above, the program searches for a dead end node. Such a
node is one where you cannot insert any mode nodes. In the tree above the node with
value 4 is a dead end as you cannot insert any of the values in that node.
The time complexity of the program is O(n) where n is the number of nodes of the BST.
# Python Program to check if there is a dead end in Binary Search Tree and print
# that value
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
# Function to insert a new Node with given key in the Binary Search Tree
def insert(node, key):
# If the tree is empty,return a new Node
if node == None:
# Otherwise, go down the tree
if key < node.data:
node.left = insert(node.left, key)
elif key > node.data:
node.right = insert(node.right, key)
return node # return the Node
# Returns true if tree with given root contains dead end or not.
# min and max indicate values allowed are from 1 to 9999999999
# 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:
return (deadEnd(root.left, Min, (root.data) - 1) or deadEnd(root.right, root.data + 1, Max))
if __name__ == '__main__':
deadEndData=deadEnd(b, 1, 9999999999)
print('No, the tree has no dead ends.')
print('Yes, the tree contains a dead end at value:')