1
$\begingroup$

Show that for any leaf v in a binary search tree, if u is the parent of v, then either key[v] is the largest key in the tree smaller than key[u], or key[v] is the smallest key in the tree larger than key[u].

I don't understand "key[v] is the largest key in the tree smaller than key[u]" and "key[v] is the smallest key in the tree larger than key[u]." Can someone help explain the problem to me?

$\endgroup$
1
$\begingroup$

In Order traversal sorts key in an ascending order. If $u$ is the parent of leaf $v$ then $v$ is either left or right child of $u$. If $v$ is left child then $key[v]\leq key[u]$ which implies $key[v]$ is the largest key in the tree smaller than $key[u]$. Similar intuition follows if $v$ is right child.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.