How to find predecessor in binary search tree

Q: What is the inorder predecessor of 15 in given binary search tree?

Here, 13 is 15s in-order predecessor.

Q: Where is the inorder predecessor of a node A in a binary search tree?

Well use a recursive approach to find the inorder predecessor of a node in a binary search tree. The idea behind the approach is simple: if the left child exists for a node, then the inorder predecessor of that node will be the maximum node in the left subtree.

Given a BST, find the inorder predecessor of a given key in it. If the key does not lie in the BST, return the previous greater node (if any) present in the BST.

Índice Show

Recursive Version
Iterative Version
How do you find the successor and predecessor of a binary tree?
What is the inorder predecessor of 15 in given binary search tree?
Where is the inorder predecessor of a node A in a binary search tree?
Does root node have predecessor?

An inorder predecessor of a node in the BST is the previous node in the inorder traversal of it. For example, consider the following tree:

The inorder predecessor of 8 does not exist.
The inorder predecessor of 10 is 8
The inorder predecessor of 12 is 10
The inorder predecessor of 20 is 16

Practice this problem

A node’s inorder predecessor is a node with maximum value in its left subtree, i.e., its left subtree’s right-most child. If the left subtree of the node doesn’t exist, then the inorder predecessor is one of its ancestors. To find which ancestors are the predecessor, move up the tree towards the root until we encounter a node that is the right child of its parent. If any such node is found, then the inorder predecessor is its parent; otherwise, the inorder predecessor does not exist for the node.

Recursive Version

We can recursively check the above conditions. The idea is to search for the given node in the tree and update the predecessor to the current node before visiting its right subtree. If the node is found in the BST, return the maximum value node in its left subtree. If the left subtree of the node doesn’t exist, then the inorder predecessor is one of its ancestors, which is already being updated while searching for the given key.

Following is the C++, Java, and Python implementation of the idea:

C++

100

101

102

103

104

105

106

107

108

109

#include <iostream>

usingnamespacestd;

// Data structure to store a BST node

struct Node

{

intdata;

Node* left=nullptr,*right= nullptr;

Node(){}

Node(intdata):data(data) {}

};

// Recursive function to insert a key into a BST

Node* insert(Node*root,intkey)

{

// if the root is null, create a new node and return it

if(root==nullptr){

returnnew Node(key);

}

// if the given key is less than the root node, recur for the left subtree

if(key<root->data){

root->left=insert(root->left,key);

}

// if the given key is more than the root node, recur for the right subtree

else{

root->right= insert(root->right,key);

}

returnroot;

}

// Helper function to find the maximum value node in a given BST

Node* findMaximum(Node*root)

{

while (root->right){

root =root->right;

}

return root;

}

// Recursive function to find inorder predecessor for a given key in the BST

Node* findPredecessor(Node*root,Node* prec,intkey)

{

// base case

if(root==nullptr){

returnprec;

}

// if a node with the desired value is found, the predecessor is the maximum

// value node in its left subtree (if any)

if(root->data== key)

{

if(root->left!=nullptr){

return findMaximum(root->left);

}

// if the given key is less than the root node, recur for the left subtree

elseif (key<root->data){

returnfindPredecessor(root->left,prec, key);

}

// if the given key is more than the root node, recur for the right subtree

else{

// update predecessor to the current node before recursing

// in the right subtree

prec=root;

return findPredecessor(root->right,prec, key);

}

returnprec;

}

intmain()

{

int keys[]={15, 10,20,8,12, 16,25};

/* Construct the following tree

/ \

10 20

/ \ / \

8 12 16 25

Node*root =nullptr;

for(int key:keys){

root =insert(root,key);

}

// find inorder predecessor for each key

for(intkey: keys)

{

Node*prec =findPredecessor(root,nullptr, key);

if(prec!= nullptr){

cout<<"The predecessor of node "<<key<<" is "<<prec->data<<endl;

}

else{

cout<<"The predecessor doesn't exist for " <<key<<endl;

}

return0;

}

Download Run Code

Java

100

101

102

103

104

105

106

107

108

109

110

111

112

// A class to store a BST node

classNode

{

intdata;

Node left=null,right= null;

Node(intdata){

this.data=data;

}

classMain

{

// Recursive function to insert a key into a BST

publicstaticNode insert(Node root,intkey)

{

// if the root is null, create a new node and return it

if(root== null){

returnnew Node(key);

}

// if the given key is less than the root node, recur for the left subtree

if(key< root.data){

root.left =insert(root.left,key);

}

// if the given key is more than the root node, recur for the right subtree

else{

root.right= insert(root.right,key);

}

returnroot;

}

// Helper function to find the maximum value node in a given BST

publicstaticNode findMaximum(Node root)

{

while(root.right !=null){

root= root.right;

}

return root;

}

// Recursive function to find inorder predecessor for a given key in the BST

public staticNode findPredecessor(Node root,Node prec,intkey)

{

// base case

if(root==null){

returnprec;

}

// if a node with the desired value is found, the predecessor is the maximum

// value node in its left subtree (if any)

if (root.data==key)

{

if(root.left!= null){

return findMaximum(root.left);

}

// if the given key is less than the root node, recur for the left subtree

elseif (key<root.data){

returnfindPredecessor(root.left,prec, key);

}

// if the given key is more than the root node, recur for the right subtree

else{

// update predecessor to the current node before recursing

// in the right subtree

prec=root;

return findPredecessor(root.right,prec, key);

}

returnprec;

}

publicstaticvoid main(String[]args)

{

int[]keys={15, 10,20,8,12, 16,25};

/* Construct the following tree

/ \

10 20

/ \ / \

8 12 16 25

Node root=null;

for (intkey:keys){

root=insert(root,key);

}

// find inorder predecessor for each key

for(int key:keys)

{

Node prec=findPredecessor(root,null, key);

if(prec!= null)

{

System.out.println("The predecessor of node "+key+" is "

+ prec.data);

}

else{

System.out.println("The predecessor doesn't exist for node "

+key);

}

Download Run Code

Python

# A class to store a BST node

classNode:

def __init__(self,data,left=None, right=None):

self.data =data

self.left=left

self.right=right

# Recursive function to insert a key into a BST

def insert(root,key):

# if the root is None, create a new node and return it

ifroot isNone:

return Node(key)

# if the given key is less than the root node, recur for the left subtree

ifkey<root.data:

root.left =insert(root.left,key)

# if the given key is more than the root node, recur for the right subtree

else:

root.right =insert(root.right,key)

returnroot

# Helper function to find the maximum value node in a given BST

deffindMaximum(root):

whileroot.right:

root =root.right

returnroot

# Recursive function to find inorder predecessor for a given key in a BST

deffindPredecessor(root,prec,key):

# base case

ifroot isNone:

returnprec

# if a node with the desired value is found, the predecessor is the maximum value

# node in its left subtree (if any)

ifroot.data==key:

if root.left:

return findMaximum(root.left)

# if the given key is less than the root node, recur for the left subtree

elifkey<root.data:

returnfindPredecessor(root.left,prec, key)

# if the given key is more than the root node, recur for the right subtree

else:

# update predecessor to the current node before recursing

# in the right subtree

prec=root

returnfindPredecessor(root.right,prec, key)

returnprec

if__name__== '__main__':

keys=[15, 10,20,8,12, 16,25]

''' Construct the following tree

/ \

10 20

/ \ / \

8 12 16 25

'''

root=None

forkey in keys:

root= insert(root,key)

# find inorder predecessor for each key

forkey inkeys:

prec= findPredecessor(root,None,key)

ifprec:

print(f'Predecessor of node {key} is {prec.data}')

else:

print('The predecessor doesn\'t exist for node', key)

Download Run Code

Output:

The predecessor of node 15 is 12
The predecessor of node 10 is 8
The predecessor of node 20 is 16
The predecessor doesn’t exist for node 8
The predecessor of node 12 is 10
The predecessor of node 16 is 15
The predecessor of node 25 is 20

The time complexity of the above solution is O(n), where n is the size of the BST, and requires space proportional to the tree’s height for the call stack.

Iterative Version

The same algorithm can be easily implemented iteratively as follows in C++, Java, and Python:

C++

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

#include <iostream>

usingnamespacestd;

// Data structure to store a BST node

struct Node

{

intdata;

Node* left=nullptr,*right= nullptr;

Node(){}

Node(intdata):data(data) {}

};

// Recursive function to insert a key into a BST

Node* insert(Node*root,intkey)

{

// if the root is null, create a new node and return it

if(root==nullptr){

returnnew Node(key);

}

// if the given key is less than the root node, recur for the left subtree

if(key<root->data){

root->left=insert(root->left,key);

}

// if the given key is more than the root node, recur for the right subtree

else{

root->right= insert(root->right,key);

}

returnroot;

}

// Helper function to find the maximum value node in a given BST

Node* findMaximum(Node*root)

{

while (root->right){

root =root->right;

}

return root;

}

// Iterative function to find inorder predecessor for a given key in a BST

Node* findPredecessor(Node*root,intkey)

{

// base case

if(root==nullptr){

returnnullptr;

}

Node*prec=nullptr;

while (1)

{

// if the given key is less than the root node, visit the left subtree

if(key<root->data){

root=root->left;

}

// if the given key is more than the root node, visit the right subtree

elseif (key>root->data)

{

// update predecessor to the current node before visiting

// right subtree

prec =root;

root=root->right;

}

// if a node with the desired value is found, the predecessor is the maximum

// value node in its left subtree (if any)

else{

if (root->left){

prec =findMaximum(root->left);

}

break;

}

// if the key doesn't exist in the binary tree, return previous greater node

if(!root){

returnprec;

}

// return predecessor, if any

returnprec;

}

intmain()

{

intkeys[]={ 15,10,20,8, 12,16,25};

/* Construct the following tree

/ \

10 20

/ \ / \

8 12 16 25

Node*root=nullptr;

for(int key:keys){

root =insert(root,key);

}

// find inorder predecessor for each key

for(intkey: keys)

{

Node*prec =findPredecessor(root,key);

if(prec!=nullptr){

cout<<"The predecessor of node "<<key<< " is "<<prec->data<<endl;

}

else{

cout<<"The predecessor doesn't exist for "<<key<<endl;

}

return 0;

}

Download Run Code

Java

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

// A class to store a BST node

classNode

{

intdata;

Node left=null,right= null;

Node(intdata){

this.data=data;

}

classMain

{

// Recursive function to insert a key into a BST

publicstaticNode insert(Node root,intkey)

{

// if the root is null, create a new node and return it

if(root== null){

returnnew Node(key);

}

// if the given key is less than the root node, recur for the left subtree

if(key< root.data){

root.left =insert(root.left,key);

}

// if the given key is more than the root node, recur for the right subtree

else{

root.right= insert(root.right,key);

}

returnroot;

}

// Helper function to find the maximum value node in a given BST

publicstaticNode findMaximum(Node root)

{

while(root.right !=null){

root= root.right;

}

return root;

}

// Iterative function to find inorder predecessor for a given key in the BST

public staticNode findPredecessor(Node root,int key)

{

// base case

if (root==null){

returnnull;

}

Node prec =null;

while(true)

{

// if the given key is less than the root node, visit the left subtree

if(key<root.data){

root=root.left;

}

// if the given key is more than the root node, visit the right subtree

elseif(key>root.data)

{

// update predecessor to the current node before visiting

// right subtree

prec =root;

root= root.right;

}

// if a node with the desired value is found, the predecessor is the

// maximum value node in its left subtree (if any)

else{

if(root.left!=null){

prec=findMaximum(root.left);

}

break;

}

// if the key doesn't exist in the binary tree,

// return previous greater node

if (root==null){

returnprec;

}

// return predecessor, if any

returnprec;

}

publicstaticvoidmain(String[] args)

{

int[]keys ={15,10,20, 8,12,16,25};

/* Construct the following tree

/ \

10 20

/ \ / \

8 12 16 25

Node root=null;

for(intkey:keys) {

root=insert(root, key);

}

// find inorder predecessor for each key

for(intkey:keys)

{

Node prec=findPredecessor(root, key);

if(prec!= null)

{

System.out.println("The predecessor of node "+key+" is "

+ prec.data);

}

else{

System.out.println("The predecessor doesn't exist for node "+ key);

}

Download Run Code

Python

# A class to store a BST node

classNode:

def __init__(self,data,left=None, right=None):

self.data =data

self.left=left

self.right=right

# Recursive function to insert a key into a BST

def insert(root,key):

# if the root is None, create a new node and return it

ifroot isNone:

return Node(key)

# if the given key is less than the root node, recur for the left subtree

ifkey<root.data:

root.left =insert(root.left,key)

# if the given key is more than the root node, recur for the right subtree

else:

root.right =insert(root.right,key)

returnroot

# Function to find the maximum value node in a given BST

deffindMaximum(root):

whileroot.right:

root =root.right

returnroot

# Iterative function to find inorder predecessor for a given key in a BST

deffindPredecessor(root,key):

# base case

ifnotroot:

returnNone

prec=None

whileTrue:

# if the given key is less than the root node, visit the left subtree

ifkey< root.data:

root= root.left

# if the given key is more than the root node, visit the right subtree

elif key>root.data:

# update predecessor to the current node before visiting

# right subtree

prec=root

root=root.right

# if a node with the desired value is found, the predecessor is the maximum

# value node in its left subtree (if any)

else:

if root.left:

prec= findMaximum(root.left)

break

# if the key doesn't exist in the binary tree, return previous greater node

ifroot isNone:

returnprec

# return predecessor, if any

returnprec

if __name__=='__main__':

keys= [15,10,20,8, 12,16,25]

''' Construct the following tree

/ \

10 20

/ \ / \

8 12 16 25

'''

root=None

forkey in keys:

root= insert(root,key)

# find inorder predecessor for each key

forkey inkeys:

prec= findPredecessor(root,key)

if prec:

print(f'Predecessor of node {key} is {prec.data}')

else:

print('The predecessor doesn\'t exist for node',key)

Download Run Code

Output:

The time complexity of the above solution is O(n), where n is the size of the BST. The auxiliary space required by the program is O(1).

Thanks for reading.

Please use our online compiler to post code in comments using C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.

Like us? Refer us to your friends and help us grow. Happy coding 🙂

How do you find the successor and predecessor of a binary tree?

Root is the given key: In this case, if the left subtree is not NULL, then predecessor is the rightmost node in left subtree and if right subtree is not NULL, then successor is the leftmost node in right subtree. Root is greater than key: In this case, the key is present in left subtree of root.

What is the inorder predecessor of 15 in given binary search tree?

Here, 13 is 15's in-order predecessor.

Where is the inorder predecessor of a node A in a binary search tree?

We'll use a recursive approach to find the inorder predecessor of a node in a binary search tree. The idea behind the approach is simple: if the left child exists for a node, then the inorder predecessor of that node will be the maximum node in the left subtree.

Does root node have predecessor?

The inorder predecessor of a node p is the node q that comes just before p in the binary tree's inorder traversal. Given the root node of a binary search tree and the node p , find the inorder predecessor of node p . If it does not exist, return null .