# Prove key of leaf is larger or smaller than key of parent if leaf is largest key in smaller tree or smallest in larger tree with respect to parent

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?

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.