 ### Python Program to find inorder predecessor and successor of a key input by the user in a Binary Search Tree(BST) without using recursion

`Python  Program to find inorder predecessor and successor of a key input by the user in a `
`Binary Search Tree(BST) without using recursion `
`In Binary Search Tree, Inorder Successor of an input node can also be defined as the node `
`with the smallest key greater than the key of input node. So, it is sometimes important to`
`find next node in sorted order.This program takes as input an integer as a key for a node`
`and finds the inorder  predecessor and successor of that node  in the BST and if none of `
`these is found or the key doesn't exist it will print appropriate message. The program `
`uses an iterative approach instead of finding the values recursively.In this program, `
```the following BST is created and used.

/*The BST tree
15
/    \
/      \
10       20
/ \      /  \
/   \    /    \
8    12  16    25
*/

The time complexity of the program is O(h) where h is the height  of the BST.
Input: A data value that is supposed to be the value of a node whose Inorder  predecessor```
`and successor is needed and a BST`
```Output: Inorder predecessor and successor of that node.

The Algorithm to find the successor is divided into two cases on the basis of right subtree```
`of the input node being empty or not.`
```1) If right subtree of node is not NULL, then successor lies in right subtree. Do following.
Go to right subtree and return the node with minimum key value in right subtree.
2) If right subtree of node is NULL, then start from root and use search like technique.```
```Do following.
Travel down the tree, if a node%u2019s data is greater than root%u2019s data then go right side,```
```otherwise go to left side.

The Algorithm to find the predecessor is divided into two cases on the basis of left ```
```subtree of the input node being empty or not.
1) If left subtree of node is not NULL, then predecessor lies in left subtree. Do following.
Go to left subtree and return the node with maximum key value in left subtree.
2) If left subtree of node is NULL, then start from root and use search like technique.```
```Do following.
Travel down the tree, if a node%u2019s data is greater than root%u2019s data then go right side, ```
```otherwise go to left side.

# Python  Program to find inorder predecessor and successor of a key input by the user in ```
```# a Binary Search Tree without using recursion

predecessor=None
successor=None
class Node:
# Constructor to create a new node
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def  insert(root,key):				#function to create a BST
if(root==None):
return Node(key)
if(key < root.data):
root.left=insert(root.left,key)
else:
root.right=insert(root.right,key)
return root

# function to find the rightmost(or maximum) value of left sub-tree of the node (if it exists)
def findMax(node):
while(node.right):
node=node.right
return node

#iterative function to find predecessor
def getPredecessor(root, val) :
global predecessor
# Base condition
if (root ==None) :
return  None
while (True):
#if key is less than root  traverse the left tree
if ( val<root.data):
root=root.left
#if key is greater than root  traverse the right tree
elif (val>root.data):
#set the predecessor to root
predecessor=root
root=root.right
#if any node has the same value as key,the predecessor is the max value
#or rightmost value of its left subtree( if one exists)
else :
if(root.left):
predecessor=findMax(root.left)
break
if(root==None):
return None
return predecessor```
```# function to find the leftmost(or minimum) value of right sub-tree of the node (if it exists)
def findMin(node):
while(node.left):
node=node.left
return node

def getSuccessor(root, val) :
global successor
# Base condition
if (root ==None) :
return  None
while (True):
#if key is less than root  traverse the left  subtree
if ( val<root.data):
#the current node(root) is set to the successor
successor=root
root=root.left
#if key is greater than root  traverse the right subtree
elif (val>root.data):
root=root.right
#if any node has the same data  value as key , the successor is the min value
#or leftmost value of its right subtree if one exists
else :
if(root.right):
successor=findMin(root.right)
break
if(root==None):
return None
return successor

# main
if __name__ == '__main__':
keys={15,10,20,8,12,16,25}
root=None
for key in keys:
root=insert(root,key)
print('Enter the value for which you want to find the predecessor and the successor:')
key=input()
pred= getPredecessor(root,int(key))
if(pred!=None):
print('Predecessor for  ' + str(key) + ' is ' + str(pred.data))
else:
print('Predecessor for  ' + str(key) + ' does not exist')

suc= getSuccessor(root,int(key))

if(suc!=None):
print('Successor for  ' + str(key) + ' is ' + str(suc.data))
else:
print('Successor for  ' + str(key) + ' does not exist')``` 