Consider the following new-order strategy for traversing a given tree: I.…
2021
Consider the following new-order strategy for traversing a given tree: I. Visit the right subtree of a node using new-order II. Visit the node III. Visit the left subtree of a node using new-order What is the new-order traversal of the given tree?
- A.
Z, V, Y, X, W, P, S, U, T, Q, R
- B.
R, Q, T, U, S, P, W, X, Y, V, Z
- C.
P, W, X, Y, V, Z, R, Q, T, U, S
- D.
S, U, T, Q, R, Z, V, Y, X, W, P
Attempted by 266 students.
Show answer & explanation
Correct answer: A
To determine the new-order traversal, follow the given strategy: I. Visit the right subtree of a node using new-order, II. Visit the node, III. Visit the left subtree of a node using new-order.
Start at the root P. The right subtree of P is V, so we first traverse the subtree rooted at V.
For node V: its right subtree is Z, so visit Z first. Then visit V. Then traverse the left subtree of V, which is W.
For node W: its right subtree is X, so visit X first. Then visit W. Then traverse the left subtree of W, which is T.
For node T: its right subtree is U, so visit U first. Then visit T. Then traverse the left subtree of T, which is empty.
After completing the right subtree of P, visit P. Then traverse the left subtree of P, which is Q.
For node Q: its right subtree is S, so visit S first. Then visit Q. Then traverse the left subtree of Q, which is R.
Combine all visited nodes in order: Z, V, Y, X, W, P, S, U, T, Q, R.