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

## Comments