Python Program to find a dead end in a Binary Search Tree(BST)

Python Program to find a dead end in a Binary Search Tree(BST)

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:
   /   \  
  3      8 
 / \       \
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

class Node:

# Constructor to create a new node
    def __init__(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:
        return Node(key)

# Otherwise, go down the tree
    if key <
        node.left = insert(node.left, key)
    elif key >
        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:
        return False

# if this occurs means dead end is present.
    if Min == Max:
        return (

    return (deadEnd(root.left, Min, ( - 1) or deadEnd(root.right, + 1, Max))

# main
if __name__ == '__main__':

    deadEndData=deadEnd(b, 1, 9999999999)
    if deadEndData==0:
        print('No, the tree has no dead ends.')
        print('Yes, the tree contains a dead end at value:')