The following numbers are inserted into an empty binary search tree in the…
2004
The following numbers are inserted into an empty binary search tree in the given order: 10, 1, 3, 5, 15, 12, 16. What is the height of the binary search tree (the height is the maximum distance of a leaf node from the root)?
- A.
2
- B.
3
- C.
4
- D.
6
Attempted by 409 students.
Show answer & explanation
Correct answer: B
Solution: Build the binary search tree by inserting the numbers in order, then find the maximum distance from root to any leaf.
Insert 10 as the root.
Insert 1: goes to the left of 10.
Insert 3: less than 10 so left; greater than 1 so right child of 1.
Insert 5: goes to the right of 3.
Insert 15: right child of 10.
Insert 12: left child of 15.
Insert 16: right child of 15.
Paths from root (10) to leaves and their distances:
10 → 1 → 3 → 5 (distance 3)
10 → 15 → 12 (distance 2)
10 → 15 → 16 (distance 2)
The maximum distance from the root to any leaf is 3.
Therefore the height of the binary search tree is 3
A video solution is available for this question — log in and enroll to watch it.