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

CONCEPT

In a binary search tree, each inserted key is compared from the root downward: a smaller key moves left and a larger key moves right until an empty child position is found.

The height used here is the maximum number of edges on a root-to-leaf path. Therefore, a path containing n nodes has n − 1 edges.

APPLICATION

1. Insert 10 as the root.

2. Insert 1 to the left of 10 because 1 < 10.

3. Insert 3 to the right of 1 because 3 < 10 but 3 > 1.

4. Insert 5 to the right of 3 because 5 < 10, 5 > 1, and 5 > 3.

5. Insert 15 to the right of 10 because 15 > 10.

6. Insert 12 to the left of 15 because 12 > 10 but 12 < 15.

7. Insert 16 to the right of 15 because 16 > 10 and 16 > 15.

CROSS-CHECK

The resulting root-to-leaf paths can be checked independently:

• 10 → 1 → 3 → 5 contains 4 nodes and 3 edges.

• 10 → 15 → 12 contains 3 nodes and 2 edges.

• 10 → 15 → 16 contains 3 nodes and 2 edges.

The maximum edge count is 3, so the height of the binary search tree is 3.