In inorder traversal, our root value comes after its left child value and before its right child value, i.e., Left -> Root -> Right.
We know that a Binary Search Tree is a Binary Tree wherethe value of every nodeof the tree is larger than the maximum value of its left subtree and lesser than the minimum value of its right subtree.
So essentially,the inorder traversal of a BST gives us elements in ascending order sorted manner.
The inorder predecessor of a node in a Binary Search Tree is the node that comes before our key node when we write the inorder traversal of the tree.
Example:
For the given BST, the inorder traversal would be: 2 3 4 5 6 7 8
Here the in-order predecessor of 4 will be 3, for 7 it will be 6 &, etc. So now we know what is the inorder predecessor of a given node in a BST.
Let’s see how we can write code for the in-order predecessor of a node in a binary search tree.
Methodology
We’ll use a recursive approach to find the in-order 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 in-order predecessor of that node will be the maximum node in the left subtree.
And if the left child is NULL for the node, then the predecessor will be one of the ancestor nodes of the node. To find that ancestor, we keep updating our predecessor node as we proceed in the right subtree.
For the task to find the inorder predecessor of a node in a binary search tree, we’ll use a recursive method.
The method signature for the Recursive Function will be like this:
void findPredecessor(Node* root, Node* &pred, int x);
The function takes three parameters:
Root Node or the Current Node
Predecessor Node (it will be null initially and passed by reference, meaning we’ll be making changes in the original node)
A key-value ‘x’ (denoting the value for which we want to find predecessor)
First, our base condition will be when the root is NULL, the pred will be NULL, and we’ll simply return.
Then we’ll check if the root value is equal to the key-value & if the left child exists, then the pred node will be the maximum node from the left subtree.
Now, if the root value is less than the key value, then we’ll update the pred node with the root node and call our findPredecessor function with root->right.
pred = root;
findPredecessor(root->right, pred, x);
At last, if the root value is greater than the key value, then we’ll have to search in the left subtree of the root for the key.
findPredecessor(root->left, pred, x);
Now let’s look at the code to find the Inorder predecessor of a node in a binary search tree in C++:
#include <iostream>
using namespace std;
// Binary Tree Node class
class Node
{
public:
int data;
Node *left;
Node *right;
Node(int x){
data = x;
left = NULL;
right = NULL;
}
};
// Insert a value in our BST
Node* insert(Node* root, int value)
{
if (root == NULL) {
return new Node(value);
}
// if root node is greater than value, insert value in left subtree
if (value < root->data) {
root->left = insert(root->left, value);
}
// if root is lesser than value, insert value in right subtree
else {
root->right = insert(root->right, value);
}
return root;
}
// Function to find maximum node in a BST
Node* maximumNode(Node* root)
{
while (root->right) {
root = root->right;
}
return root;
}
// Pred node is passed by reference meaning it is making changes in the original node
void findPredecessor(Node* root, Node*& pred, int key)
{
// base case
if (root == NULL)
{
pred = NULL;
return;
}
// if the root is our key node then the predecessor will be the largest node in its left subtree
if (root->data == key)
{
if (root->left != NULL) {
pred = maximumNode(root->left);
}
}
// if our key value is less than the root node value then we'll search in left subtree for key node
else if (key < root->data) {
findPredecessor(root->left, pred, key);
}
// if our key value is more than the root node value then we'll search in right subtree for key node
else if (key > root->data) {
// update predecessor to the current node before recursing in the right subtree
pred = root;
findPredecessor(root->right, pred, key);
}
return;
}
int main()
{
Node* root = NULL;
int n=0;
// Taking BST as input
while(n!=-1) {
cin>>n;
root = insert(root, n);
}
// Here we'll take input x and then find it's predecessor
int x;
cin>>x;
Node* pred = NULL;
findPredecessor(root, pred, x);
// -1 will always be the first node in Inorder traversal because we are taking input BST till -1
// that means the node with predecessor -1 is the first node in Inorder traversal
if(pred->data != -1) cout << "The predecessor of node " << x << " is " << pred->data;
else cout << "The predecessor of node doesn't exist";
return 0;
}
Sample Input 1:
5 3 2 4 7 6 8 -1
8
Sample Input 2:
5 3 2 4 7 6 8 -1
4
Sample Output 1:
The predecessor of node 8 is 7
Sample Output 2:
The predecessor of node 4 is 3
Time Complexity
The Time Complexity to find inorder predecessor of a node in a binary search tree is O(n), where ‘n’ is the number of nodes in the Binary Search Tree.
Space Complexity
The space complexity to find in-order predecessor of a node in a binary search tree is O(h), where ‘h’ is the height of the Binary search tree.
The space complexity can also be written as O(log2n).
A Binary Tree is a generic tree with every node having at most two children. In generic trees, a node can have any number of children, but in binary trees, a node can only have a left and a right child.
What are Binary Search Trees?
A Binary Search Tree is a Binary Tree where the value of every node of the tree is larger than the maximum value of its left subtree and lesser than the minimum value of its right subtree.
Why are Binary Search Trees used?
In Binary Search Trees, the searching becomes very fast compared to the Binary Trees because, at each node, we can judge if we should go to left subtree or right subtree (i.e., if the key value is lesser than the node value, then we’ll go to left subtree to search our key node & if the key value is greater than the node value we’ll proceed to right subtree to search our key node). The time complexity to search an element is O(log2n), where n is the number of nodes in the binary search tree.
What is an in-order predecessor in a binary search tree?
The in-order predecessor of a node in a Binary Search Tree is the node that comes before our key node when we write the inorder traversal of the tree.
What are the time and space complexities of finding an in-order predecessor in a binary search tree?
Time Complexity: O(n), where ‘n’ is the number of nodes in BST Space complexity: O(h) or O(log2n), where ‘h’ is the height of BST and ‘n’ is the number of nodes in BST.
Conclusion
Cheers if you reached here!! You learned something new today.
In this blog, we saw how to find the in-order predecessor of a node in a binary search tree.
Suppose the interviewer is judging your DSA knowledge. In that case, there is a high probability that he will ask you questions from Binary search trees and amongst the binary search tree interview questions on traversals - finding the in-order predecessor of a node in a binary search tree is one of the most commonly asked questions.
305+ registered