Question

Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let \( T \) be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of \( T \) is __________. (Answer in integer)

Hint:

In a Binary Search Tree (BST), the depth of a node is the number of edges from the root to that node.

Answer 1

Constructing the binary search tree:

• 10 is the root.
• -4 goes to the left of 10.
• 15 goes to the right of 10.
• 30 goes to the right of 15.
• 20 goes to the left of 30.
• 5 goes to the right of -4.
• 60 goes to the right of 30.
• 19 goes to the left of 20.

The path from 19 to the root 10 follows these steps:
\( 19 \to 20 \to 30 \to 15 \to 10 \) (4 edges). This path is traced by moving from node 19 up to the root, traversing through the parent nodes at each step until reaching 10.
Thus, the answer is 4 as there are 4 edges in this path.