Finding Inorder Successor of a node in a Binary Search Tree

Akshat Chaturvedi
Last Updated: May 13, 2022

Introduction

Before diving into our topic, “Inorder Successor of a given key In Binary Search Tree.” Let’s first understand basic terms related to our topic.

 

So what is an INORDER Traversal?

It is one of the ways to traverse the given binary tree such that the elements are ordered in such a way that the left node comes before the root node, and the right node comes after the root node.

LEFT -> ROOT -> RIGHT

 

We can remember this by the keyword ‘IN’, meaning that the root node should come in between the left and right nodes.

Similarly, in pre-order and post-order, the root node should come ‘PRE’ (before left node) and POST’ (after right node), respectively.

 

OKAY, now that the inorder traversal is clear, let’s see the main properties of Binary Search Trees.

A Binary Search Tree is a Binary Tree (obviously), so in BSTs, each node can have at most two children. But BSTs also have one interesting property: each node in a BST is greater than the maximum node in its left subtree and lesser than the minimum node in its right subtree.

 

Let’s see an example:

If we observe the given Binary Tree, we can tell that it is a Binary Search Tree because the value of each node is greater than the maximum valued node in its left subtree and is lesser than the minimum valued node in its right subtree.

For instance, take node 50, the maximum valued node in its left subtree is 45, and the minimum valued node in its right subtree is 55.

 

If we print the Inorder Traversal for this BST, we’ll get:

10 35 40 45 50 55 70 100 150

 

See, the elements are in ascending order. That brings us to another interesting fact related to BSTs: the inorder traversal of a BST gives us elements in ascending order sorted manner.

 

NOW, coming on to the main topic of this blog, “Inorder Successor of a given key In Binary Search Tree.”

 

The Inorder Successor of a given key in the Binary Search Tree is the node that appears just after the provided key node in the inorder traversal of the BST.

 

From our above example, we can say that the Inorder Successor of, let’s say, 35 is 40 because, in the inorder traversal of BST, it is coming just after 35. For 50, it will be 55, and so on.

 

Kudos! Now you have understood all the essential things needed, and the only thing left is to write code to find the inorder successor of a given key In Binary Search Tree.

 

Methodology

I will explain an iterative approach to solve this problem which is mostly similar to the recursive approach that I have described in my previous blog, “Finding inorder predecessor of a node in a Binary Search Tree” you can check out this blog LINK.

If you want to implement this problem recursively, then only some slight tweaks will be there in the code that you can easily figure out!

 

The main idea behind the approach is that if the right child exists for a node, then the inorder successor of that node will be the minimum node in the right subtree.

 

But if the right child doesn’t exist for the node, then the successor will be one amongst the ancestor nodes of the node. To find that ancestor, we keep updating our successor node as we proceed in the left subtree.

The updation is done because if we are moving towards the left subtree, then there has to be an inorder successor for every node in the left subtree, and the maximum value of that successor would be root.

 

Let’s clear this with an example (refer to the tree above):

If we are currently at node 50 and our key is 40 (finding inorder successor of 40 in Binary Search Tree), we’ll check in the left subtree because 40<50.

Before going to the left subtree we’ll update our successor to 50 because the maximum value of a successor of any node in the left subtree can be 50.

 

NOW, let’s look at the code to find the Inorder successor of a given key in 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 minimum node in a BST

Node* minimumNode(Node* root)

{

    while (root->left) {

        root = root->left;

    }

    return root;

}

 

// succ node is passed by reference meaning it is making changes in the original node

void findSuccessor(Node* root, Node*& succ, int key)

{

    succ = NULL;

    

    while(1){

        

        // if the root is our key node then the successor will be the smallest node in its right subtree

        if (root->data == key)

        {

            if (root->right != NULL) {

                succ = minimumNode(root->right);

            }

            break;

        }

     

        // 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) {

            // update successor to the current node before searching in left subtree

            succ = root;

            root = root->left;

        }

     

        // 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) {

            root = root->right;

        }

        

        // simply return if the key value doesn't exist in tree

        if(root == NULL) return;

    }

    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 successor

    int x;

    cin>>x;

    Node* succ = NULL;

    

    // NULL valued pred variable is passed to the function

    findSuccessor(root, succ, x);

    

    

    if(succ != NULL) cout << "The inorder successor of node " << x << " is " << succ->data;

    else cout << "The inorder successor of node doesn't exist";

 

    return 0;

}

 

 

Sample Input:

8 10 12 15 16 20 25 -1

20

 

Sample Output:

The inorder successor of node 20 is 25

 

Time Complexity

The time complexity to find the inorder successor of a given key in Binary Search Tree (Iteratively) is O(n), where n is the number of nodes in BST.

 

Space Complexity

The space complexity to find the inorder successor of a given key in Binary Search Tree (Iteratively) is O(1).

The recursive approach requires space proportional to the function call stack, but it is constant with the iterative approach.

 

FAQs

  1. What is a Binary Tree?
    A Binary Tree is a generic tree with every node having at most two children. A node can have any number of children in generic trees, but in binary trees, a node can only have a left and a right child.
     
  2. 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.
     
  3. 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.
     
  4. What is an inorder Successor in a binary search tree?
    The Inorder Successor of a given key in Binary Search Tree is the node that appears just after the provided key node in the inorder traversal of the BST.
     
  5. What are the time and space complexities of finding an inorder Successor in a binary search tree?
    Time Complexity: O(n), where ‘n’ is the number of nodes in BST.
    Space complexity: O(1), or we can say that it has a constant space complexity.

Key Takeaways

Give yourself a pat on the back if you reach here!!

Through this blog, we learned a couple of new things and most importantly, how to find the Inorder Successor of a given key in a Binary Search Tree.

From this link, you can go through my blog “Finding the inorder predecessor of a node in a Binary Search Tree.” I have thoroughly described finding a given key’s predecessor in a BST with a Recursive approach.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think