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

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?


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