algorithmdata-structuresbinary-search-treetree-traversal

Is the Inorder Predecessor of a Node with a Left Subtree Always a Leaf Node in a Binary Search Tree?


In a Binary Search Tree (BST), I am trying to understand the properties of the inorder predecessor, particularly for nodes that have a left subtree.

Definition: The inorder predecessor of a node is the maximum node in its left subtree.

Observation: I'm curious if the inorder predecessor is always a leaf node when the node in question has a left subtree.

Consider the following BST:

      5
     / \
    3   7
   / \
  2   4

In this tree:

The inorder predecessor of node 3 (which has a left subtree) is 2. Node 2 is a leaf node.

Questions:

Is my understanding correct?

Are there any exceptions to this rule?

What are the general properties of inorder predecessors in BSTs?

Thank you for your help!


Solution

  • This is not (always) true.

    If a node 𝑢 has a left subtree rooted at 𝑣, then 𝑢's inorder predecessor is the node 𝑤 with the greatest key in that subtree rooted by 𝑣. 𝑤 is the node that sits at the end of the longest downward path from 𝑤 that includes no left-directed edge. By consequence, 𝑤 (the inorder predecessor) has no right subtree. But there is no constraint on its potential left subtree.

    For example, take this binary search tree:

                        ___20___
                       /        \
                    __8__        30
                   /     \      /
                  4      12    23
                 / \     /    /  \
                2   6  10    21   27
               /   /  /  \       /
              1   5  9   11     25
    

    The predecessor of 4 is 2, which has a left child (1). The predecessor of 8 is 6, which also has a left child (5). The predecessor of 20 is 12, which has a left subtree (rooted at 10). The predecessor of 30 is 27, which has a left child (25). Examples enough to show that these predecessors do not have to be leaves.

    The common invariant is that these predecessors have no right child.

    What are the general properties of inorder predecessors in BSTs?

    In general -- so not only when looking at nodes that have a left subtree -- a node's predecessor could be any node in the BST, except for the node having the greatest value. This is obviously the case, because all these nodes have a successor, and so they are their successor's predecessor.

    In particular, when a node has no left subtree, then its predecessor (if any) is necessarily a node with a right subtree. This is the opposite condition as we have for your case, and so there is no identifying property for predecessors in terms of the presence of a left or right subtree.