ITPEC FE Morning April 2021 Question 8
The in-order traversal of a binary tree is a procedure that visits all nodes of the tree. For a non-empty binary tree T, it performs the following operations in order.
Which of the following is the ordered sequence of nodes when the in-order traversal is performed on the binary tree below?
Explanation
7, 4, 8, 2, 5, 1, 3, 9, 6 — in-order visits the whole left subtree, then the node, then the right subtree.
The tree: root 1 with children 2 and 3; 2 has children 4 and 5; 4 has children 7 and 8; 3 has only a right child 6; 6 has only a left child 9.
- •Left subtree of 1, rooted at 2: in-order of 4 gives 7, 4, 8; then 2; then 5
- •Root: 1
- •Right subtree of 1, rooted at 3: 3 has no left child, so 3; then in-order of 6 gives 9, 6
Answer (c)
Why not others:
- •(a) — node first, then left, then right: pre-order
- •(b) — the in-order sequence written backwards, which is right, node, left
- •(d) — left, right, then node: post-order, which always ends at the root 1
Key rule: In-order puts every node between its left and right subtrees, pre-order starts at the root and post-order ends at it; expand one subtree at a time.
Algorithm and Programming · AI-written, may contain errors
This question comes from an official ITPEC past paper. ITPEC Practice is an independent study tool and is not affiliated with ITPEC. See the official FE past-paper collection or Report an issue.