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.
Prove that if x has a predecessor, this predecessor has a right child
binary search trees
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.