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:

     5   
   /   \  
  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):
        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.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:
        return False

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


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

# main
if __name__ == '__main__':
    deadEndData=0
    b=Node(5)
    insert(b,3)
    insert(b,8)
    insert(b,10)
    insert(b,1)
    insert(b,4)
    insert(b,2)

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