Home Practice Programming Inorder Successor of a Node in Binary Search Tree

Inorder Successor of a Node in Binary Search Tree

Given a pointer to a node of a Binary Search Tree(BST), we have to find the next node, which is the Inorder successor of the given node (assume a pointer to a parent node is already given).

In Binary Search Tree, the inorder successor of a node is a node that appears after the given node in Inorder traversal of a Binary Search Tree. Since, the Inorder traversal of a Binary Search Tree is all elements in sorted order, hence Inorder successor of an input node is be defined as the next node with the smallest key value, but greater than the key value of the input node.

Consider the following Binary Search Tree,

              15
            /    \
          8       25
        /  \     /  \
       4    9   20   30

The inorder successor of node 15 is 20, the inorder successor for node 9 is 15, while the inorder successor for the node 30, doesn’t exist.

Algorithm

If a node has a right subtree, then according to the inorder traversal the next will be the leftmost(minimum) element of the right subtree. For example, the next node in inorder traversal for 15 in the above tree will be 20(leftmost element of the right subtree).

But if the current node doesn’t have the right subtree?

If a given node doesn’t have the right subtree just like node 9, in such case traverse the tree up using the parent pointer(we are given a pointer to the parent node) and see if the node is the left child of a parent pointer. If yes then stop otherwise(if the node is the right child of its parent) keep traversing up.

next_node(temp)
{
    if(temp == NULL)
        return NULL;
        
    /*if right subtree exist return the 
     minimun node in right subtree */
    if(temp->right != NULL){
	temp = temp->right;
	while(temp->left!=NULL)
		temp = temp->left;
	return temp;
    }
   
    /*right subtree doesn't exit, then
    go to the parent of current node */
    parent = temp->parent;

    /* if the current node is left child of parent,
     then stop, otherwise keep traversing up until
     we don't the node is not left child of its 
     parent or the current node is the last node */
    while(parent!=NULL && parent->right == temp){
	temp = parent;
	parent = temp->parent;
    }

    return parent;
}

Implementation of the above algorithm in CPP

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

class Node{
    public:
        int data;
        Node *left;
        Node *right;
        Node *parent;

    public:
        Node(int x){
            data = x;
            left = NULL;
            right = NULL;
            parent = NULL;
        }
};

Node *tree_node(Node* tree, int val){

    if(tree == NULL)
        return (new Node(val));

    Node *temp;

    if(tree->data >= val){
        temp = tree_node(tree->left, val);
        tree->left = temp;
        temp->parent = tree;
        
    }
    else{
        temp = tree_node(tree->right, val);
        tree->right = temp;
        temp->parent = tree;
        
    }

    return tree;
}

Node* next_node(Node *temp)
{
    if(temp == NULL)
        return NULL;

    if(temp->right != NULL){
        temp = temp->right;
        while(temp->left!=NULL)
            temp = temp->left;

        return temp;
    }
    
    Node *parent = temp->parent;
    while(parent!=NULL && parent->right == temp){
        temp = parent;
        parent = temp->parent;
    }

    return parent;
}

int main()
{
    Node *tree = NULL; 
    tree = tree_node(tree, 15);
    tree = tree_node(tree, 8);
    tree = tree_node(tree, 25);
        tree = tree_node(tree, 30);
    tree = tree_node(tree, 4);
    tree = tree_node(tree, 9);
    tree = tree_node(tree, 20);

    
    Node *temp = tree->left->right;
    Node *res = next_node(temp);

    if(res!=NULL)
        cout<<"Inorder successor of "<<temp->data<<" = "<<res->data<<endl;
    else
        cout<<"Inorder successor of "<<temp->data<<" doesn't exist"<<endl;

    return 0;
}
Output

Inorder successor of 9 is 15

Time Complexity

The time complexity of the above algorithm is O(H), where H is the height of a given Binary Search Tree. In the worst case, the height of the tree will be N, where N is the number of nodes(in the tree in case of left or right-skewed tree) hence the time complexity in the worst case will be O(N).

Please comment if you want to add more information or found anything incorrect about the above explanation.

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Subscribe to our weekly newsletter

Join our community of 1000+ developers and stay updated with the fast moving world of computer science

We promsie, we won't spam
Even we hate spam as much as you hate them

Books recommendation for interview preparation