The inorder and preorder traversal of a binary tree are d b e a f c g and a b…
2007
The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
- A.
d e b f g c a
- B.
e d b g f c a
- C.
e d b f g c a
- D.
d e f g b c a
Attempted by 285 students.
Show answer & explanation
Correct answer: A
Solution: Reconstruct the tree from preorder and inorder, then produce postorder.
Root is a (first in preorder).
In inorder, nodes left of a are d, b, e → left subtree; nodes right of a are f, c, g → right subtree.
Left subtree: preorder segment b d e gives root b. In inorder d b e shows left child d and right child e, so left-subtree postorder is d e b.
Right subtree: preorder segment c f g gives root c. In inorder f c g shows left child f and right child g, so right-subtree postorder is f g c.
Full postorder is left-subtree postorder, then right-subtree postorder, then root: d e b f g c a.
Postorder traversal: d e b f g c a
A video solution is available for this question — log in and enroll to watch it.