 ### 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:`
```     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.

# 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__':
b=Node(5)
insert(b,3)
insert(b,8)
insert(b,10)
insert(b,1)
insert(b,4)
insert(b,2) 