If the postorder traversal of an expression tree is 8, 2, +, 5, /, what is the preorder traversal?
A)/, +, 2, 8, 5
B)8, +, 2, /, 5
C)/, +, 8, 2, 5
D)+, /, 8, 2, 5

Question

Quizplus · Accepted Answer

In an expression tree, the postorder traversal lists operands first, followed by their operators. To find the preorder traversal, we start with the last operator in the postorder as the root. The postorder given is 8, 2, +, 5, /, indicating that '/' is the root operator. The expression before '/' (8, 2, +) forms the left subtree, and '5' is the right subtree. The left subtree, when reconstructed, has '+' as the root with '8' and '2' as leaves. Therefore, the preorder traversal starts with the root '/', followed by the root of the left subtree '+', then its leaves '8' and '2', and finally the right subtree '5', making the correct preorder traversal /, +, 8, 2, 5.

If the Postorder Traversal of an Expression Tree Is 8