Inorder Successor in Binary Tree

Introduction

Binary trees are the specialized version of generic trees where every node can have only two children viz. the left child and the right child of a binary tree. In the following article, we are going to discuss some approaches for obtaining the inorder successor of a node in a binary tree.

Inorder traversal of the tree dictates that the nodes be processed in the left, root and the right manner, i.e., the leftmost child is printed first, then the root node, and finally the right child of the root node. Now since you have a basic understanding of the term inorder, let’s move on to the question. We are asked to print the inorder successor of a node in a binary tree.

The in-order successor of a node implies that we have to return the node which will come next in the inorder traversal of a binary tree. Let us see an example:

The inorder traversal for the above binary tree is: 4 2 5 1 6 3 7

In the above example, the inorder successor of 4 is 2. Similarly, the inorder successor of 5 is 1. Now it is natural to wonder what if the inorder successor of the last node is asked? What then? Well, it's pretty simple since there is no inorder successor for the last node (here 7) we simply consider NULL as their inorder successor. Therefore the inorder successor of 7 here is NULL.

Now that the term inorder successor of a binary tree is clear, let's move on towards an algorithm that will help us find the inorder successor of a given node in a binary tree.

Before moving forward to the solution it is recommended to try the problem by yourself first. Inorder Successor Problem

Approach 1

While discussing this approach, you have to keep this one thing in mind, i.e., Inorder traversal of a binary tree follows the order: Left child of node----> node -----> Right child of the node. Let us discuss the cases we need to consider while finding the inorder successor of a given node.

Case 1. The right child of the given node exists

Suppose the right child of the given binary tree is not NULL, then, in this case, the inorder successor of the given node will be the leftmost child of the right subtree.

Case 2. The right child of the given node is NULL

Now let’s discuss the case where a right child of a given binary tree is NULL i.e the tree is not having any right subtree. Think about this! So in this case it will travel up to the binary tree to find the parent node and will check if the current node is the left child of that parent node. If yes then stop you have found your answer; otherwise, continue traversing up the binary tree.

Case 3. The given node is the rightmost node of the binary tree

Suppose we are asked to give the inorder successor of the node which is the rightmost node of the binary tree. In this case, the answer will be NULL as discussed in the example above for node 7.

Let us now implement the above-discussed approach to find the inorder successor of a given node in the binary tree.

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

//Binary Tree Node class
class Node {
    public:
    //data members
    int data;
    Node * left;
    Node * right;

    //constructor
    Node(int data) {
        this -> data = data;
        this -> left = NULL;
        this -> right = NULL;
    }

};

// function for finding the leftmost node in a tree
Node * leftMost(Node * node) {
    while (node != NULL && node -> left != NULL)
        node = node -> left;
    return node;
}

// function for finding the rightmost node in a tree
Node * rightMost(Node * node) {
    
    while (node != NULL && node -> right != NULL)
        node = node -> right;
    return node;
}

// recursive function for finding the Inorder Successor
Node * temp = new Node(-1);
Node * findInorderRecursive(Node * root, Node * x) {
    if (root == NULL)
        return NULL;

    if (root == x || (temp = findInorderRecursive(root -> left, x)) ||
        (temp = findInorderRecursive(root -> right, x))) {
        if (temp) {
            if (root -> left == temp) {
                cout << "Inorder Successor of " << x -> data;
                cout << " is " << root -> data << "\n";
                return NULL;
            }
        }

        return root;
    }

    return NULL;
}

// Function for finding the inorder successor of given target node x
void getInorderSuccessor(Node * root, Node * x) {
    // Case1: If right child of given node is not NULL
    if (x -> right != NULL) {
        //leftmost child of right subtree will be the ans
        Node * inorderAns = leftMost(x -> right);
        cout << "Inorder Successor of " << x -> data << " is ";
        cout << inorderAns -> data << "\n";
    }

    // Case2: If right child of given node is NULL
    if (x -> right == NULL) {
        Node * ans = rightMost(root);

        // Case3: If x is the last node in the right subtree
        if (ans == x)
            cout << "No inorder successor exist because it is the right most node.\n";
        else
            //traverse up the tree
            findInorderRecursive(root, x);
    }
}

// Driver program to test above functions
int main() {
    //creating the binary tree
    Node * root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node(7);

    // Case 1: When the right child of the target node is not NULL.
    getInorderSuccessor(root, root);

    // Case 2: When the right child of the target node is NULL
    getInorderSuccessor(root, root -> left -> left);

    // Case 3: When the target node is the rightmost node of the binary tree
    getInorderSuccessor(root, root -> right -> right);

    return 0;
}

Output:

Inorder Successor of 1 is 6
Inorder Successor of 4 is 2
No inorder successor exists because it is the rightmost node.

Complexity Analysis

Time Complexity: The time complexity of the above approach is O(N), where N is the number of nodes in the binary tree.

Space Complexity: The space complexity of the above approach is O(H), where H is the height of the binary tree. There can be a skewed tree where H will be equal to the number of nodes in the binary tree for the worst-case scenario. Hence in the worst-case space complexity will be O(N).

As is with most problems, there can be multiple possible solutions for this one as well. Let us discuss another approach:

Approach 2

In this approach, we will do the reverse inorder traversal of the binary tree, and once we find the element for which we were finding an inorder successor, then the last tracked element will be our answer. You know what an inorder traversal is like we have discussed in this blog above. Now you just need to reverse it. Try coding this out on your own, and then check your answer with the below-given code.

C++ Implementation

#include<bits/stdc++.h>
using namespace std;

//Binary Tree Node class
class Node {
    public:
    //data members
    int data;
    Node * left;
    Node * right;

    //constructor
    Node(int data) {
        this -> data = data;
        this -> left = NULL;
        this -> right = NULL;
    }

};

// Function that prints the inorder successor of the target node by performing a reversed inorder traversal of the tree. Next will point to the last tracked node in the reversed inorder traversal.
void getInorderSuccessor(Node * root,
    Node * targetNode,
    Node * & next) {
    // if root is null then return
    if (root == NULL)
        return;

    getInorderSuccessor(root -> right, targetNode, nextNode);

    // if we found the target node 
    if (root -> data == targetNode -> data) {
        if (next Node == NULL)
            cout << "inorder successor of " <<
            root -> data << " is: null\n";
        else
            cout << "inorder successor of " <<
            root -> data << " is: " <<
            nextNode -> data << "\n";
    }
    nextNode = root;
    getInorderSuccessor(root -> left, targetNode, nextNode);
}

// Driver Code
int main() {
    Node * root = new Node(1);
    root -> left = new Node(2);
    root -> right = new Node(3);
    root -> left -> left = new Node(4);
    root -> left -> right = new Node(5);
    root -> right -> left = new Node(6);
    root -> right -> right = new Node(7);

    Node * next = NULL;

    // Case 1 : When the right child of the target node is not NULL
    getInorderSuccessor(root, root, next);

    // Case 2: When the right child of the target node is NULL
    next = NULL;
    getInorderSuccessor(root, root -> left -> left, next);

    // Case 3: When the target node is the rightmost node of the binary tree
    next = NULL;
    getInorderSuccessor(root, root -> right -> right, next);

    return 0;
}

Output:

inorder successor of 1 is: 6
the inorder successor of 4 is: 2
the inorder successor of 7 is: null

Complexity Analysis

Time Complexity: The time complexity of the above approach is O(N), where N is the number of nodes in the binary tree.

Space Complexity: The space complexity of the above approach is O(H), where H is the height of the binary tree. For the worst-case scenario, there can be a skewed tree where H will be equal to the number of nodes in the binary tree. Hence in the worst-case space complexity will be O(N).

Frequently Asked Questions

What is meant by a Binary tree?

A generic tree where each node can have two children at most is known as a binary tree.

Can I find an inorder successor of the binary tree in less than O(H) time complexity?

No, you can’t because, to get the inorder successor of a node in a binary tree, you need to travel at least H nodes where H refers to the height of the binary tree.

What will be the inorder successor of the last node in the inorder traversal?

The inorder successor of the rightmost node, i.e., the last in-order traversal node in inorder traversal, will be NULL.

What is the order of traversal of nodes in inorder traversal?

In the inorder traversal, you first have to print the left child of the node, then the node itself, and then its right child has to be printed.

Conclusion

So far we have discussed two approaches for obtaining the inorder successor of a binary tree. One of the key takeaways here is that the inorder successor of the rightmost node in the binary tree is NULL. Both the approaches give us the inorder successor of a node in O(H) time complexity, where H refers to the height of the binary tree. If you would like to know more about Traversals in Binary Trees follow this link

Check out some suggested problems to check your understanding:

Hungry for more? Check out some of our products to quench your thirst for knowledge:

Happy Coding :)