The following numbers are inserted into an empty binary search tree in the…

Solution:

Insert the numbers into a binary search tree in the given order and track where each goes.

1. Insert 10 as the root.

2. Insert 1 as left child of 10.

3. Insert 3 as right child of 1.

4. Insert 5 as right child of 3.

5. Insert 15 as right child of 10.

6. Insert 12 as left child of 15.

7. Insert 16 as right child of 15.

Resulting important root-to-leaf paths:

• 10 → 1 → 3 → 5 (4 nodes, 3 edges)

• 10 → 15 → 12 (3 nodes, 2 edges)

• 10 → 15 → 16 (3 nodes, 2 edges)

Definition: the height of a tree is commonly taken as the number of edges on the longest root-to-leaf path.

Therefore the height is 3 (from the path 10 → 1 → 3 → 5).