-2
$\begingroup$

In a BST, Let x be a leaf node, which is a left child of node y. Prove that if x has a predecessor, this predecessor has a right child.

How can I tackle this question? I'm not even sure from where to start.

$\endgroup$
1
  • 1
    $\begingroup$ Draw the tree . $\endgroup$
    – quicksort
    Jan 18 '17 at 22:30
1
$\begingroup$

In-order traversal (which is the case for a BST) starts at the leftmost leaf. This disqualifies the leftmost leaf from being the node in question since it would have no predecessor. All other leafs qualify. For all right leaves it follows that the predecessor has a right child (since the predecessor to any right leaf is it's parent). For all left leafs that are no the first leaf their predecessor is it's grandparent, which must have a right subtree for the leaf to exist. Ergo if a left leaf has a predecessor then this predecessor has a right subtree.

http://www.sqa.org.uk/e-learning/LinkedDS04CD/images/pic013.jpg

$\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.