Project ForgeThe 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
- d e b f g c a
- Be d b g f c a
- Ce d b f g c a
- Dd e f g b c a
Explanation
Root = 'a' (from preorder). Inorder splits at 'a': left subtree inorder = 'd b e', right subtree inorder = 'f c g'. Left subtree's preorder (next 3) = 'b d e' → root 'b', splitting 'd b e' gives left child 'd', right child 'e'. Right subtree's preorder (last 3) = 'c f g' → root 'c', splitting 'f c g' gives left child 'f', right child 'g'. Postorder (left,right,root recursively): for b-subtree: d,e,b; for c-subtree: f,g,c; then a. Full postorder: d e b f g c a.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.