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.