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?