What You'll Learn
You'll learn how to find the inorder predecessor—the node that comes immediately before a given node in sorted order within a Binary Search Tree.
What Is the Inorder Predecessor?
The inorder predecessor of a node is the node that would appear directly before it if you performed an inorder traversal (left-root-right). Since inorder traversal of a BST visits nodes in ascending order, the predecessor is simply the next smaller value.
Two Cases to Consider
Finding the predecessor follows a clear logic based on the tree's structure:
Case 1: Node Has a Left Subtree
If the node has a left child, the predecessor is the rightmost (maximum) node in that left subtree. Think of it like this: you go left once (to get smaller values), then keep going right as far as possible to find the largest of those smaller values.
50
/
30
\
40 ← predecessor of 50
Case 2: No Left Subtree
If there's no left child, you must travel up the tree. The predecessor is the first ancestor where you arrived from a right turn—meaning the first ancestor that is smaller than your current node.
50
\
70 ← you're here
/
60 ← predecessor (50 is the ancestor from a right turn)
If you never took a right turn going up (always coming from left children), there is no predecessor—you're at the minimum node.
Analogy
Imagine a sorted phone book. Your predecessor is the entry right before yours. If there are entries indented under you to the left, pick the last one in that group. Otherwise, backtrack to find who you're nested under from the right side.
Key Takeaway: The inorder predecessor is either the maximum value in the left subtree, or the nearest ancestor reached via a right-child link.