What is the inorder predecessor of 15 in the binary search tree shown below?

Concept

An inorder traversal of a binary search tree visits the keys in ascending order, so the inorder predecessor of a node is the largest key in the tree that is smaller than that node’s key.

When a node has a left subtree, that largest smaller key is always the rightmost node of that left subtree: step once to the left child, then keep following right-child links until you reach a node that has no right child.

Applying the rule to 15

1. The target node 15 is the root, and it does have a left subtree, rooted at 6. So the rightmost-node rule applies.

2. Step once to the left child: the descent is now standing at 6.

3. Follow the right-child link of 6: the descent moves to 7.

4. Follow the right-child link of 7: the descent moves to 13.

5. 13 has no right child — its single child, 9, hangs on the left — so the rightward descent stops here.

6. The rightmost node of the left subtree of 15 is therefore 13, and the inorder predecessor of 15 is 13.

Cross-check

• Writing out the whole inorder traversal gives 2, 3, 4, 6, 7, 9, 13, 15, 17, 18, 20. The key that sits immediately before 15 in this ascending list is 13, which matches the descent above.

• 13 is also the largest key in the tree smaller than 15: the remaining keys below 15 are 2, 3, 4, 6, 7 and 9, and every one of them is smaller than 13.

• The inorder successor obeys the mirror rule — the leftmost node of the right subtree — which would step to 18 and then left to 17. Mixing the two rules up is the usual source of error on this pattern.