I'm trying to understand the rules for finding the inorder predecessor of a node in a binary search tree (BST).
If a node π₯ has a left subtree, the inorder predecessor is the largest value in that left subtree.
If node π₯ has no left subtree, the predecessor is one of its ancestors. But if node π₯ is the right child, then its parent p is its predecessor
Hereβs my specific question:
If node π₯ has no left subtree and is a left child of its parent, its parent π cannot be the predecessor because π is larger than π₯. In this case, we move up the tree to find the ancestor that is smaller than π₯, and that ancestor is π₯'s predecessor.
Take a look at this BST:
50
/ \
30 70
/ \
20 40
/
35
Is it true that the inorder predecessor of node π₯ in this situation is always its grandparent, or could it be a more distant ancestor?
The node you seek is the closest (lowest) ancestor, for whom the node in question is a right-side descendant, if such ancestor exists.
Example
In a tree like this
4
\
8
/ \
7 9
/
6
/
5
the predecessor of 5 is 4, which is not its grandparent (that is 7).
It is, however, the closest ancestor of 5, for which 5 is its right-side descendant (for all closer ancestors, that is for 6, 7 and 8, the 5 is a left-side descendant).