Course contentsShow
← Computer Science
Lesson 511 of 2,87212. Binary Search TreesFree lesson

Finding Inorder Successor

Locate the inorder successor: the leftmost node in the right subtree or the first ancestor from a left turn.

Finding Inorder Successor

What you'll learn: You'll learn how to find the next node in sorted order after a given node in a binary search tree.

What Is an Inorder Successor?

The inorder successor of a node is the node that would come immediately after it if you performed an inorder traversal (left-root-right). Since inorder traversal of a BST gives sorted order, the successor is simply the next larger value.

Two Cases to Consider

Finding the successor depends on the node's structure:

Case 1: Node Has a Right Subtree

If the node has a right child, the successor is the leftmost node in the right subtree (the minimum value in that subtree). Why? Because it's the smallest value that's still larger than our current node.

Think of it like this: you need someone taller than you. If there are people to your right, pick the shortest person from that group.

Case 2: Node Has No Right Subtree

If there's no right subtree, you must travel up the tree to find the first ancestor where you arrived from a left turn. This ancestor is the first node larger than your current node.

Analogy: Imagine climbing a mountain path. When you can't go right anymore, you backtrack upward until you reach a junction where you originally came from the left branch—that's your next destination.

Example

      15
     /  \
    10   20
   /  \    \
  5   12   25
  • Successor of 10: has right child → leftmost in right subtree = 12
  • Successor of 12: no right child → first ancestor from left turn = 15
  • Successor of 25: no right child, no ancestors from left → null

Key Takeaway: The inorder successor is either the minimum node in the right subtree, or the nearest ancestor reached by a left turn—whichever applies to your node's position.