Search code examples
algorithmbinary-search-treetree-traversalinorder

Is the inorder predecessor of a node with no left subtree and being the left child of its parent always its grandparent?

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
  • Node 𝑥 = 35 has no left subtree and is the left child of its parent
  • 40 (the parent) cannot be the inorder predecessor because it's larger than 35.
  • We move up the tree to the parent of 40, which is 30.
  • 30 is smaller than 35, so 30 is the inorder predecessor of 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?

Solution

  • 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).