 ### Python program to find inorder successor in binary search tree with recursion.

Description :

In Binary Tree, Inorder successor of a node is the next node in Inorder traversal of the Binary Tree. Inorder Successor is NULL for the last node in Inorder traversal.
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 algoritham is divided into two parts, on the basis of right subtree of the input node being empty or not.

Steps

1)If right subtree of node is not NULL, then succ 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 successor  is one of the ancestors. Do following. Travel up using the parent pointer until you see a node which is left child of it%u2019s parent. The parent of such a node is the successor.

Program:

# A binary tree node
class Node:

# Constructor to create a new node
def __init__(self, key):
self.data = key
self.left =
None
self.right =
None

def inOrderSuccessor(root, n):

# Step 1 of the above algorithm
if n.right is not None:
return minValue(n.right)

# Step 2 of the above algorithm
p = n.parent
while( p is not None):
if n != p.right :
break
n = p
p = p.parent
return p

# Given a non-empty binary search tree, return the minimum data value found in that tree. Note that the entire tree doesn't need to be searched
def minValue(node):
current = node

# loop down to find the leftmost leaf
while(current is not None):
if current.left is None:
break
current = current.left

return current

# Given a binary search tree and a number, inserts a new node with the given number in the correct place in the tree. Returns the new root pointer which the
#caller should then use( the standard trick to avoid
# using reference parameters)
def insert( node, data):

# 1) If tree is empty then return a new singly node
if node is None:
return Node(data)
else:

# 2) Otherwise, recur down the tree
if data <= node.data:
temp = insert(node.left, data)
node.left = temp
temp.parent = node
else:
temp = insert(node.right, data)
node.right = temp
temp.parent = node

# return the unchanged node pointer
return node

# Driver progam to test above function

root =
None

# Creating the tree given in the above diagram
root = insert(root,
20)
root = insert(root,
8);
root = insert(root,
22);
root = insert(root,
4);
root = insert(root,
12);
root = insert(root,
10);
root = insert(root,
14);
temp = root.left.right.right

succ = inOrderSuccessor( root, temp)
if succ is not None:
print ("\nInorder Successor of %d is %d " %(temp.data , succ.data) )
else:
print ("\nInorder Successor doesn't exist")

Output:

Inorder Successor of 14 is 20

>>> #### More Articles of Khushboo Singh:

Name Views Likes
Python program to insert an element in binary tree. 867 20
Tokenize text using NLTK in Python. 1251 12
Python Remove multiple elements from list while Iterating. 774 22
Python How to Check if an item exists in list ? 4323 14
Python How to remove multiple elements from list ? 788 26
Python program to check if two trees are mirror of each other without using recursion. 695 19
Python program to find maximum in Binary tree. 974 19
Python Check if all elements are same using Set 752 15
Python program to find diameter of a binary tree. 1127 20
Python program to print root to leaf paths without using recursion. 870 20
Python program to find root of the tree where children id sum for every node is given. 710 23
Introduction of Python NLTK library 1405 25
Categorizing and Tagging Sentences using NLTK in Python . 1063 19
Python program to find height of a tree without using recursion. 690 16
Python program to find sum of all nodes of the given perfect binary tree. 697 19
Python program to find minimum in binary tree. 860 23
Python Check if element exist in list using list.count() function. 724 13
Python program to convert a given binary tree to doubly linked list. 923 20
Python program to find distance between two nodes of a binary tree. 1561 20
NLTK stop Words 1196 13
Python program to find largest binary search tree in a Binary Tree. 973 20
Python program to find inorder successor in binary search tree with recursion. 1246 18
Python program to convert a binary tree into doubly linked list in spiral fashion. 828 15
Python List check if element are same using all() 713 12
Python program to check if two trees are identical using recursion. 739 30
Python Find the occurrence count of an element in the tuple using count() 1001 23
Python Convert two lists to a dictionary 761 19
Python program to construct a complete binary tree from given array. 1480 14
Python program to find diameter of binary tree in O(n). 908 17
Introduction to the AVL tree. 810 15
Python program to check if two trees are identical without using recursion 693 17
Python Convert a list of tuples to dictionary. 1134 24
Python program to convert a binary tree to a circular doubly link list. 688 21
Python Check if element exist in list based on own logic. 787 23
Python program to merge two binary trees by doing node sum using recursion 1043 27
Python program to check whether a given binary tree is perfect or not. 712 17
Python Check if all elements are same using list.count(). 1126 28
Python program to find an element into binary tree 658 12
Python program to find lowest common ancestor in a binary tree 1254 24