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')