The in-order successor in a binary search tree problem

Key takeaways:
The in-order successor in a binary search tree is the node with the smallest key greater than the current node's key.
Finding the in-order successor is a common task when performing deletions, updates, or search operations in BSTs.
The time complexity of finding an in-order successor is proportional to the height of the tree, with $O(h)$ being the best and worst cases for balanced and unbalanced trees, respectively.
The space complexity of this algorithm is constant, $O(1)$ , as it only uses a fixed amount of extra space.

What is an in-order successor?

In a binary search tree (BST), the in-order successor of a node is the one that appears immediately after it in an in-order traversal. This concept is crucial for navigating BSTs, particularly during operations like deletion, updating, or searching. Since an in-order traversal of a BST produces nodes in sorted order, the in-order successor is the next greater node. Identifying this successor is a key step in many tree-based algorithms. Before delving into this Answer, it would be helpful to look at an overview of binary search trees.

Problem statement

The in-order successor of a node in a binary search tree is the node with the smallest key that is larger than the key of the given node. In this task, the goal is to find and return this successor when a specific node in the tree is provided.

Constraints:

$1\leq$ nodes $\leq100$
$-10^4\leq$ nodes.data $\leq10^4$

Examples

In-order successor in a binary search tree

What is the in-order successor of a 9 in the following tree?

Question 1 of 30 attempted

Finding in-order successor in a BST

This solution finds the inorder successor of a given node in the binary search tree. Because a binary search tree maintains the property where left children are smaller and right children are larger than the parent node, the solution uses this property to find the in-order successor without visiting all nodes. To locate the successor:

If the target node has a right child, its successor is the smallest node in the right subtree.
If there is no right child, the successor lies in one of the ancestors. We must traverse the tree, keeping track of the last node where we turned left, as that node will be the closest greater value.

Here’s the step-by-step implementation of the solution:

Initialize an empty node to return the result. This variable will store the in-order successor.
Begin at the root of the binary search tree.
Loop through the tree:
- If the node value we need to find the successor of is greater than or equal to the current node’s value, move to the right subtree (no need to check the left subtree as the value is greater).
- If the value is less than the current node’s value, update the result node to the current root node and move to the left subtree.
The result node will eventually hold the in-order successor. If the result remains None after the loop, there is no in-order successor in the binary search tree.

Python code

Let’s look at the Python code for the algorithm we just discussed.

# Class definition for a binary tree node
class Tree:
    def __init__(self, data=0, left=None, right=None):
        self.data = data  # The value stored in the node
        self.left = left  # Pointer to the left child
        self.right = right  # Pointer to the right child
# Function to find the inorder successor of a given node in a BST
def inorder(root, node):
    # Variable to store the potential inorder successor
    result = None  
    # Traverse the tree starting from the root
    while root:
        if node.data >= root.data:
            # If the node's value is greater than or equal to the current root's value,
            # move to the right subtree (no inorder successor in the left subtree)
            root = root.right
        else:
            # If the node's value is less than the current root's value,
            # update the result as the current root (potential successor)
            # and move to the left subtree to check for a smaller successor
            result = root
            root = root.left
    
    # Return the inorder successor if found, otherwise None
    return result  
# Driver code
def main():
  root = Tree(10)
  root.left = Tree(5)
  root.right = Tree(20)
  root.left.left = Tree(3)
  root.left.right = Tree(8)
  root.right.left = Tree(15)
  root.right.right = Tree(25)
  
  node = root.left.right
  successor = inorder(root, node)
  
  if successor:
      print(f"The inorder successor of {node.data} is", successor.data)
  else:
      print(f"There is no inorder successor of {node}")
if __name__ == '__main__':
  main()

Time complexity

The time complexity of this code is $O(h)$ , where $h$ is the height of the binary search tree. In the worst case, the function traverses from the root to a leaf node. Since the tree is a binary search tree, its height determines the traversal time. For a balanced BST, the height is proportional to $log~n$ , resulting in a time complexity of $O(log~n)$ . However, in the worst-case scenario, such as a skewed tree, the height could be proportional to the number of nodes, leading to a time complexity of $O(n)$ , where $n$ is the total number of nodes.

Space complexity

The space complexity of this code is $O(1)$ . This is because the code only uses a constant amount of space for the variables. No extra data structures like arrays or lists are used, and the space required does not grow with the size of the input. Thus, the space complexity remains constant.

Practice resources

If you further want to explore the binary search tree problems, here are some of the problems solved by different coding patterns:

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is the in-order successor in a binary search tree?

The in-order successor of a node in a binary search tree is the node with the smallest key greater than the key of the given node.

How do we find the in-order successor of a node?

The process involves traversing the tree. If the node’s value is greater than the current node’s value, move right; if it is smaller, update the result and move left.

What is the time complexity of finding the in-order successor?

The time complexity is $O(h)$ , where $h$ is the height of the tree. For a balanced tree, $h$ is logarithmic $O(log\ n)$ , but for a skewed tree, it could be linear $O(n)$ .

What happens if there is no in-order successor of a given node?

If there is no in-order successor, the function will return NULL, indicating that there is no such node in the tree.

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments