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