15.4. Predecessor Function

Try these first

1. 1.

   What is the minimum value in a BST with root value 8 and left children 7, 6, 5?

   Hint

   Traverse to the left-most node.

2. 2.

   What is the maximum value in a BST with root 10 and right children 12, 14, 16?

   Hint

   Find the right-most node.

3. 3.

   What value does the method to find a minimum return?

   • The maximum value
   • The left-most node
   • The right-most node

   Hint

   Think about how we traverse left.

4. 4.

   True or False: The predecessor of a node with children both left and right is always the maximum of the left subtree.

   • True
   • False

   Hint

   Which subtree gives a maximum value?

5. 5.

   Given a BST containing numbers 3, 5, 2, 8, find the predecessor and successor for node 3.

   Hint

   Calculate both branches and pick the respective nodes.

6. 6.

   Explain what happens when trying to find the successor of the maximum node in a BST.

   Hint

   What defines the concept of a maximum node in a BST?