سوال ۶۸ کنکور ارشد علوم کامپیوتر ۱۳۹۸

The tree

The BST has root $a$ with the structure:

        a
       / \
      b   f
     / \   \
    c   d   g
         \  /
          e h

That is: $a$ has left child $b$ and right child $f$; $b$ has children $c$ (left) and $d$ (right); $d$ has right child $e$; $f$ has right child $g$; and $g$ has left child $h$.

Deleting a node with two children

The root $a$ has two children, so it cannot simply be unlinked. The standard rule is to overwrite the deleted node's key with either:

• its in-order predecessor — the largest key in the left subtree (rightmost node), or
• its in-order successor — the smallest key in the right subtree (leftmost node).

Either choice preserves the BST ordering, since both are immediate neighbors of the root in the sorted (in-order) sequence.

Find predecessor and successor

In-order predecessor (rightmost of the left subtree rooted at $b$): follow right pointers as far as possible.

$b \to d \to e \quad(\,e \text{ has no right child}\,) \;\Rightarrow\; \textbf{predecessor} = e.$

In-order successor (leftmost of the right subtree rooted at $f$): follow left pointers as far as possible. But $f$ has no left child, so the leftmost node is $f$ itself.

$f \;(\,\text{no left child}\,) \;\Rightarrow\; \textbf{successor} = f.$

Conclusion

The root can be replaced by $f$ (successor) or $e$ (predecessor) — option 2.

Quick sanity check via the in-order (sorted) sequence: $c,\,b,\,d,\,e,\,a,\,f,\,g,\,h$. The two values flanking $a$ are exactly $e$ and $f$.

Pitfall: The successor is the leftmost node of the right subtree, not the deepest node. Here $f$ has no left child, so $f$ itself is the successor — don't wander down to $h$. Likewise the predecessor is the rightmost node of the left subtree ($e$), not the leftmost ($c$).