The inorder and preorder traversals 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
Computers and Technology · College · Wed Jan 13 2021
Answered on
The postorder traversal of the binary tree is (A) d e b f g c a.
To determine the postorder traversal of the binary tree, let's use the provided inorder and preorder traversals:
Inorder traversal: d b e a f c g
Preorder traversal: a b d e c f g
The general order of traversals is:
Preorder: Root -> Left -> Right
Inorder: Left -> Root -> Right
Postorder: Left -> Right -> Root
From the preorder traversal, we know that the first element is the root (a). Then, from the inorder traversal, we can identify the left and right subtrees based on the root.
The root is "a":
Inorder: [d b e] a [f c g]
Preorder: a [b d e] [c f g]
This divides the tree into left and right subtrees:
Left subtree (inorder): d b e
Left subtree (preorder): b d e
Right subtree (inorder): f c g
Right subtree (preorder): c f g
Now, let's focus on the left and right subtrees.
For the left subtree:
Inorder: d b e
Preorder: b d e
The root of the left subtree is "b":
Inorder: [d] b [e]
Preorder: b [d] [e]
This indicates that "b" is the root, "d" is on its left, and "e" is on its right.
For the right subtree:
Inorder: f c g
Preorder: c f g
The root of the right subtree is "c":
Inorder: f [c] g
Preorder: [c] f g
This indicates that "c" is the root, "f" is on its left, and "g" is on its right.
Therefore, the postorder traversal of the binary tree is obtained by visiting nodes in the order Left -> Right -> Root:
Left subtree: d e b
Right subtree: f g c
Root: a
So, combining these traversals, the correct postorder traversal of the binary tree is:
d e b f g c a
Therefore, the correct answer is (A) d e b f g c a.