Considering the height of a binary tree as the number of edges between the…
2018
Considering the height of a binary tree as the number of edges between the tree's root and its furthest leaf, what is the height of the binary search tree created using the following key values (in order)?
19, 14, 18, 15, 16, 13, 12
Answer: B. 4 — In a Binary Search Tree (BST), every key is inserted starting at the root: at each node, a smaller key is sent into the left subtree and a larger key into the…
- A.
3
- B.
4
- C.
5
- D.
6
Attempted by 426 students.
Show answer & explanation
Correct answer: B
In a Binary Search Tree (BST), every key is inserted starting at the root: at each node, a smaller key is sent into the left subtree and a larger key into the right subtree. The height of the tree is defined here as the number of edges on the longest root-to-leaf path, so links are counted, not nodes.
Insert 19, 14, 18, 15, 16, 13, 12 in order and track where each key lands:
19 is inserted first, so it becomes the root.
14 is smaller than 19, so it becomes the left child of 19.
18 is smaller than 19 but larger than 14, so it becomes the right child of 14.
15 is smaller than 19, larger than 14, but smaller than 18, so it becomes the left child of 18.
16 is smaller than 19, larger than 14, smaller than 18, but larger than 15, so it becomes the right child of 15.
13 is smaller than 19 and smaller than 14, so it becomes the left child of 14.
12 is smaller than 19, smaller than 14, and smaller than 13, so it becomes the left child of 13.
This insertion sequence produces two root-to-leaf paths: 19 -> 14 -> 18 -> 15 -> 16, and 19 -> 14 -> 13 -> 12.
Counting edges (not nodes) along each path shows which is longer: the first path has 4 edges (19-14, 14-18, 18-15, 15-16) across 5 nodes, while the second has 3 edges (19-14, 14-13, 13-12) across 4 nodes. The first path is longer, so it sets the tree's height.
Therefore, the height of this BST, measured in edges, is 4.