Practice question · Put in order
A binary search tree has root 5. The root's left child is 3 and its right child is 8; node 3 has left child 2 and right child 4. Order the values as an in-order traversal visits them.
- 5
- 8
- 3
- 4
- 2
Hints
- In-order means: visit the whole left subtree, then the node, then the whole right subtree.
- Apply the rule to node 3 first, before the root is visited at all.
Show the answer
- 2
- 3
- 4
- 5
- 8
Why
In-order gives 2, 3, 4, 5, 8, the values in sorted order, which is the defining property of an in-order traversal of a BST. Visiting the root first would be pre-order and would give 5, 3, 2, 4, 8, which is not sorted; the difference is only where the node itself is visited.
Practise Trees and Hierarchical Storage
The app has 5 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Trees and Hierarchical Storage
- Searching a balanced binary search tree of 1023 nodes takes at most 10 comparisons; scanning a list of the…
- Inserting 1, 2, 3, 4, 5, 6, 7, 8 into an empty binary search tree in that order produces a tree of height 8…
- A binary search tree built from sorted input degrades to a linked list, and the fix, AVL or red-black, adds…
- Select every statement the lesson supports about binary search trees.