Exam-style question
Try this first
Trace a binary tree search for the value 65 using this tree: root 50; the left child of 50 is 30; the right child of 50 is 80; the left child of 80 is 65; the right child of 80 is 90. State the values examined, in order, and explain why each branch is selected.
Model answer
What a good answer should say
- The values examined are 50, 80, and 65.
- The search starts at 50.
- Since 65 is greater than 50, it moves to the right child, 80.
- Since 65 is less than 80, it moves to the left child, 65.
Explanation
Why this works
A correct trace records the root first, followed by one node from each selected branch. The comparisons with 50 and 80 determine the right and then left movements.
Common mistake
No common mistake is linked to this question yet.