Inorder Successor in Binary Search Tree

Companies:
  • Amazon Interview Questions
  • Bloomberg Interview Questions
  • Facebook Interview Questions
  • Microsoft Interview Questions

Problem Statement

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Sample Test Case

Input: root = [2,1,3], p = 1

  2
 / \
1   3

Output: 2
Input: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1

Output: null

Problem Solution

A node’s inorder successor is node with least value in its right subtree i.e. its right subtree’s left most child.

If right subtree of the node doesn’t exists, then inorder successor is one of the ancestors of it.

To find which ancestor is the successor we can go up from the bottom of the tree towards the root until we encounter a node which is left child of it’s parent. If any such node is found, the inorder successor is its parent else inorder successor do exists for that node.

We can iteratively check above conditions. The idea is to search for given node in the tree and update the successor to current node before visiting its left subtree.

If node is found in the BST, then we return least value node in its right subtree and if the right subtree of the node doesn’t exists, the inorder successor is one of the ancestors of it which is already been updated while searching for the given key.

Complexity Analysis

Time Complexity: O(h), where h is the height of the tree.
there could be a case (suppose skewed tree) in which we have to travel all the way towards the root.

Space Complexity: O(1) as we are not using any new data structure to store.

Code Implementation

#include<iostream>
using namespace std;
 class Node {
     public:
    int data;
     Node *left;
     Node *right;
};

//Function to find some data in the tree
Node* Find(Node*root, int data) {
    if(root == NULL) return NULL;
    else if(root->data == data) return root;
    else if(root->data < data) return Find(root->right,data);
    else return Find(root->left,data);
}

//Function to find Node with minimum value in a BST
 Node* FindMin( Node* root) {
    if(root == NULL) return NULL;
    while(root->left != NULL)
        root = root->left;
    return root;
}

//Function to find Inorder Successor in a BST
 Node* Getsuccessor( Node* root,int data) {
    // Search the Node - O(h)
     Node* current = Find(root,data);
    if(current == NULL) return NULL;
    if(current->right != NULL) {  //Case 1: Node has right subtree
        return FindMin(current->right); // O(h)
    }
    else {   //Case 2: No right subtree  - O(h)
         Node* successor = NULL;
         Node* ancestor = root;
        while(ancestor != current) {
            if(current->data < ancestor->data) {
                successor = ancestor; // so far this is the deepest node for which current node is in left
                ancestor = ancestor->left;
            }
            else
                ancestor = ancestor->right;
        }
        return successor;
    }
}

//Function to visit nodes in Inorder
void Inorder(Node *root) {
    if(root == NULL) return;

    Inorder(root->left);       //Visit left subtree
    cout<<root->data;  //Print data
    Inorder(root->right);      // Visit right subtree
}

// Function to Insert Node in a Binary Search Tree
Node* Insert(Node *root,char data) {
    if(root == NULL) {
        root = new Node();
        root->data = data;
        root->left = root->right = NULL;
    }
    else if(data <= root->data)
        root->left = Insert(root->left,data);
    else
        root->right = Insert(root->right,data);
    return root;
}

int main() {
    /*Code To Test the logic
      Creating an example tree
                5
               / \
              3   10
             / \   \
            1   4   11
    */
    Node* root = NULL;
    root = Insert(root,5); root = Insert(root,10);
    root = Insert(root,3); root = Insert(root,4);
    root = Insert(root,1); root = Insert(root,11);

    //Print Nodes in Inorder
    cout<<"Inorder Traversal: ";
    Inorder(root);
    cout<<"\n";

    // Find Inorder successor of some node.
     Node* successor = Getsuccessor(root,1);
    if(successor == NULL) cout<<"No successor Found\n";
    else
    cout<<"Successor is "<<successor->data<<"\n";
}

 

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]