BST Successor Search

Hard

In a Binary Search Tree (BST), an Inorder Successor of a node is defined as the node with the smallest key greater than the key of the input node (see examples below). Given a node inputNode in a BST, you’re asked to write a function findInOrderSuccessor that returns the Inorder Successor of inputNode. If inputNode has no Inorder Successor, return null.

Explain your solution and analyze its time and space complexities.

In this diagram, the inorder successor of 9 is 11 and the inorder successor of 14 is 20.

Example:

In the diagram above, for inputNode whose key = 11

Your function would return:

The inorder successor node whose key = 12

Need a refresher on Binary Search Trees? Check out Exponent's lesson on Trees and take this interactive BST visualizer out for a spin.

Look again at the examples above (both the diagram and the text below.) Can you discern the two different cases in which a node is an Inorder Successor of a given input node?

Did you start by searching the root and traversing the tree in a binary search manner? While this works, see if you can come up with a solution that doesn't require the root.

Let’s denote the Inorder Successor of inputNode as successorNode. To arrive to the solution, we distinguish between two cases:

inputNode has a right child. In this case successorNode would be the node with the minimum key in inputNode's right subtree.
inputNode doesn't have a right child. In this case successorNode would be one of inputNode's ancestors. More specifically, within inputNode's ancestor chain (starting from inputNode all the way up to the root), successorNode is the first parent that has a left child in that chain.

If inputNode doesn't have a right child and all of its ancestors are right children to their parents, inputNode doesn't have a successor (successorNode would be null).

So why is this always true? Well, if inputNode was inserted to the tree prior to successorNode, then since successorNode.key is greater than inputNode.key, but also smaller than all other keys greater than successorNode.key, successorNode has to be in inputNode's right subtree.

Now, if inputNode was inserted to the tree after successorNode was, then since inputNode.key is smaller than successorNode.key, but also larger than all other keys smaller than successorNode.key, inputNode has to be in successorNode's left subtree.

Pseudocode:


function findInOrderSuccessor(inputNode):
    if (inputNode.right != null):
        # return the node with minimum key in the right subtree
        return findMinKeyWithinTree(inputNode.right)

    ancestor = inputNode.parent
    child = inputNode

    # travel up using the parent pointer until you see
    # a node which is the left child of its parent. The parent
    # of such a node is successorNode.
    while (ancestor != null AND child == ancestor.right):
        child = ancestor
        ancestor = child.parent

    return ancestor

function findMinKeyWithinTree(inputNode):
    while (inputNode.left != null):
        inputNode = inputNode.left

    return inputNode

Time Complexity: in both cases where either inputNode has a right child or doesn’t have one, we are visiting only O(H) number of nodes, where H is the height of the BST. For a balanced BST, since H = log(N), where N is the number of nodes in the BST, the time complexity is O(log(N)). For an unbalanced BST, the time complexity is O(N).

Space Complexity: throughout the entire algorithm we used only a constant amount of space, hence the space complexity is O(1).

def find_in_order_successor(self, inputNode):
    if inputNode.right is not None:
        # return the node with the minimum key in the right subtree
        return self.find_min_key_within_tree(inputNode.right)

    ancestor = inputNode.parent
    child = inputNode

    # Travel up using the parent pointer until you see
    # a node which is the left child of its parent. The parent
    # of such a node is successorNode.
    while ancestor is not None and child == ancestor.right:
        child = ancestor
        ancestor = child.parent

    return ancestor

def find_min_key_within_tree(self, inputNode):
    while inputNode.left is not None:
        inputNode = inputNode.left

    return inputNode

Community solutions

💬 Community guidelines

Stay on topic. Use this section for submitting solutions and providing feedback to others.
Be inclusive. Exponent is a diverse community. Please respect others' opinions and beliefs.

How would you answer? Submit your response below and get feedback from the community.

Jack99 620

March 15, 2025

C++

Node* getLeftMostChild(Node* node){
   while(node->left){
      node = node->left;
   }

   return node;
}

Node* findInOrderSuccessor( Node *inputNode )
{

  int val = inputNode->key;

  if(inputNode->right){

      return getLeftMostChild(inputNode->right);
   }else{
      inputNode  =  inputNode->parent;
      while(inputNode && inputNode->key < val){
         inputNode = inputNode->parent;
      }

      return inputNode;
   }

}

Rohan M.6

July 29, 2025

My solution is simple; it does an in-order DFS traversal to create an array of in-order elements then it searches through the array to find the node we want the successor of. finally we return the node that is 1 after the input node, in the case our input node is the last element of our DFS we know there is no successor, therefore it returns None/null.

Python

#########################################################
# CODE INSTRUCTIONS:                                    #
# 1) The method findInOrderSuccessor you're asked      #
#    to implement is located at line 30.                #
# 2) Use the helper code below to implement it.         #
# 3) In a nutshell, the helper code allows you to       #
#    to build a Binary Search Tree.                     #
# 4) Jump to line 88 to see an example for how the      #
#    helper code is used to test findInOrderSuccessor.  #
#########################################################

from typing import Optional

# A node 
class Node:
    # Constructor to create a new node
    def __init__(self, key: int):
        self.key: int = key 
        self.left: Optional['Node'] = None
        self.right: Optional['Node'] = None
        self.parent: Optional['Node'] = None

# A binary search tree 
class BinarySearchTree:
    
    # Constructor to create a new BST
    def __init__(self):
        self.root: Optional[Node] = None 

    def find_in_order_successor(self, inputNode: Node) -> Optional[Node]:
        # your code goes here
        root = self.root
        dfsArr = []
        

        def dfs(root):
            if not root:
                return 
            dfs(root.left)
            dfsArr.append(root)
            dfs(root.right)
            
        dfs(root)
        pos = 0
        for i in range(len(dfsArr)):
            if dfsArr[i] == inputNode:
                pos = i

        if pos+1 <= len(dfsArr)-1:
            return dfsArr[pos+1]
        else:
            return None

    # Given a binary search tree and a number, inserts a
    # new node with the given number in the correct place
    # in the tree. Returns the new root pointer which the
    # caller should then use(the standard trick to avoid 
    # using reference parameters)
    def insert(self, key: int) -> None:
    
        # 1) If tree is empty, create the root
        if (self.root is None):
            self.root = Node(key)
            return
        
        # 2) Otherwise, create a node with the key
        #    and traverse down the tree to find where to
        #    to insert the new node
        currentNode = self.root
        newNode = Node(key)
        while(currentNode is not None):
      
            if(key < currentNode.key):
                if(currentNode.left is None):
                    currentNode.left = newNode;
                    newNode.parent = currentNode;
                    break
                else:
                    currentNode = currentNode.left;
            else:
                if(currentNode.right is None):
                    currentNode.right = newNode;
                    newNode.parent = currentNode;
                    break
                else:
                    currentNode = currentNode.right;

    # Return a reference to a node in the BST by its key.
    # Use this method when you need a node to test your
    # findInOrderSuccessor function on
    def getNodeByKey(self, key: int) -> Optional[Node]:
    
        currentNode = self.root
        while(currentNode is not None):
            if(key == currentNode.key):
                return currentNode
            
            if(key < currentNode.key):
                currentNode = currentNode.left
            else:
                currentNode = currentNode.right
            
        return None
        
######################################### 
# Driver program to test above function #
#########################################

# Create a Binary Search Tree
bst = BinarySearchTree()
bst.insert(20)
bst.insert(9)
bst.insert(25)
bst.insert(5)
bst.insert(12)
bst.insert(11)  
bst.insert(14)    

# Get a reference to the node whose key is 9
node: Optional[Node] = bst.getNodeByKey(9)

# Find the in order successor of test
succ: Optional[Node] = bst.find_in_order_successor(node)

# Print the key of the successor node
if succ is not None:
    print(f"\nInorder Successor of {node.key} is {succ.key}")
else:
    print("\nInorder Successor doesn't exist")

Sam J.

Member

297

October 21, 2023

Java

Node findInOrderSuccessor(Node inputNode) {
      // your code goes here
      int key = inputNode.key;
      Node currentNode = this.root;
      Node succ = null;
      while(currentNode != null){
        if(currentNode.key > key){
          succ = currentNode;
          currentNode = currentNode.left;
        } else {
          currentNode = currentNode.right;
        }
      }
      return succ;
    }

Akash C.1.1k

December 23, 2024

Python

#########################################################
# CODE INSTRUCTIONS:                                    #
# 1) The method findInOrderSuccessor you're asked      #
#    to implement is located at line 30.                #
# 2) Use the helper code below to implement it.         #
# 3) In a nutshell, the helper code allows you to       #
#    to build a Binary Search Tree.                     #
# 4) Jump to line 88 to see an example for how the      #
#    helper code is used to test findInOrderSuccessor.  #
#########################################################

from typing import Optional

# A node 
class Node:
    # Constructor to create a new node
    def __init__(self, key: int):
        self.key: int = key 
        self.left: Optional['Node'] = None
        self.right: Optional['Node'] = None
        self.parent: Optional['Node'] = None

# A binary search tree 
class BinarySearchTree:
    
    # Constructor to create a new BST
    def __init__(self):
        self.root: Optional[Node] = None 

    def find_in_order_successor(self, inputNode: Node) -> Optional[Node]:
        successor = None
        current = self.root

        while current:
            if inputNode.key < current.key:
                successor = current
                current = current.left
            else:
                current = current.right
        return successor

    # Given a binary search tree and a number, inserts a
    # new node with the given number in the correct place
    # in the tree. Returns the new root pointer which the
    # caller should then use(the standard trick to avoid 
    # using reference parameters)
    def insert(self, key: int) -> None:
    
        # 1) If tree is empty, create the root
        if (self.root is None):
            self.root = Node(key)
            return
        
        # 2) Otherwise, create a node with the key
        #    and traverse down the tree to find where to
        #    to insert the new node
        currentNode = self.root
        newNode = Node(key)
        while(currentNode is not None):
      
            if(key < currentNode.key):
                if(currentNode.left is None):
                    currentNode.left = newNode;
                    newNode.parent = currentNode;
                    break
                else:
                    currentNode = currentNode.left;
            else:
                if(currentNode.right is None):
                    currentNode.right = newNode;
                    newNode.parent = currentNode;
                    break
                else:
                    currentNode = currentNode.right;

    # Return a reference to a node in the BST by its key.
    # Use this method when you need a node to test your
    # findInOrderSuccessor function on
    def getNodeByKey(self, key: int) -> Optional[Node]:
    
        currentNode = self.root
        while(currentNode is not None):
            if(key == currentNode.key):
                return currentNode
            
            if(key < currentNode.key):
                currentNode = currentNode.left
            else:
                currentNode = currentNode.right
            
        return None
        
######################################### 
# Driver program to test above function #
#########################################

# Create a Binary Search Tree
bst = BinarySearchTree()
bst.insert(20)
bst.insert(9)
bst.insert(25)
bst.insert(5)
bst.insert(12)
bst.insert(11)  
bst.insert(14)    

# Get a reference to the node whose key is 9
node: Optional[Node] = bst.getNodeByKey(9)

# Find the in order successor of test
succ: Optional[Node] = bst.find_in_order_successor(node)

# Print the key of the successor node
if succ is not None:
    print(f"\nInorder Successor of {node.key} is {succ.key}")
else:
    print("\nInorder Successor doesn't exist")

See community answers

Next Lesson

Software Engineering Introduction

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

System Design Interviews

Overview

Networking & API Design

Scalable Systems

Databases

Distributed Systems

Real-time & Events: Mock Interviews

Media & Content Delivery: Mock Interviews

Async & Data Processing: Mock Interviews

Payments & Marketplaces: Mock Interviews

Distributed Infrastructure: Mock Interviews

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

Software Engineering Introduction

Software Engineering Coding Questions

Overview

Fast Track

Time & Space Complexity

Coding Patterns

Arrays

Hash Tables

Searching & Sorting

String Manipulation

Graphs

Trees

Stacks & Queues

Linked Lists

Heaps

Recursion & Backtracking

Dynamic Programming

System Design Interviews

Overview

Networking & API Design

Scalable Systems

Databases

Distributed Systems

Real-time & Events: Mock Interviews

Media & Content Delivery: Mock Interviews

Async & Data Processing: Mock Interviews

Payments & Marketplaces: Mock Interviews

Distributed Infrastructure: Mock Interviews

Behavioral Interviews: A Practical Guide for Engineers

Fast Track (Start Here)

Theory

Tactics

Mock Interviews & Analyses

Practice

BST Successor Search