This set of Data Structures & Algorithms Multiple Choice Questions & Answers (MCQs) focuses on “Postorder Traversal”.
1. Find the postorder traversal of the binary tree shown below.
A) P Q R S T U V W X
B) W R S Q P V T U X
C) S W T Q X U V R P
D) S T W U X V Q R P
Explanation: The left subtree is traversed first, followed by the right subtree, and finally the current node in postorder traversal. S W T Q X U V R P is the posturer traversal of the tree.
2. For a binary tree the first node visited in in-order and post-order traversal is same.
Explanation: Consider a binary tree,
Its in-order traversal – 13 14 16 19
Its post-order traversal- 14 13 19 16. Here the first node visited is not same.
3. The pre-order and in-order are traversals of a binary tree are T M L N P O Q and L M N T O P Q. Which of following is post-order traversal of the tree?
A) L N M O Q P T
B) N M O P O L T
C) L M N O P Q T
D) O P L M N Q T
Explanation: The tree generated by using given pre-order and in-order traversal is
Thus, L N M O Q P T will be the post-order traversal.
4. A full binary tree can be generated using ______
A) post-order and pre-order traversal
B) pre-order traversal
C) post-order traversal
D) in-order traversal
Explanation: In a complete binary tree, each node has either 0 or 2 children. If one of the traversals is in order, a binary tree can be formed. Using post-order and pre-order traversals, however, we can create a complete binary tree.
5. The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is ______
D) any number
Explanation: Post-order and pre-order traversals are equivalent in a tree with just one node.
6. The steps for finding post-order traversal are traverse the right subtree, traverse the left subtree or visit the current node.
Explanation: In post-order traversal, the left subtree is traversed first, followed by the right subtree, and finally the output current node.
7. Which of the following pair’s traversals on a binary tree can build the tree uniquely?
A) post-order and pre-order
B) post-order and in-order
C) post-order and level order
D) level order and preorder
Explanation: Post-order and in-order traversals may be used to build a binary tree in a special way.
8. The post-order traversal of a binary tree is O P Q R S T. Then possible pre-order traversal will be ________
A) T Q R S O P
B) T O Q R P S
C) T Q O P S R
D) T Q O S P R
Explanation: The root and its right child are the last and second last nodes visited in post-order traversal, respectively. Since nodes O, P are visited after nodes Q, R, S, Option T Q R S O P cannot be a pre-order traversal. Option T O Q R P S is invalid because the given pre-order sequence and post-order traversal result in a tree with node T as root and node O as left subtree. T Q O P S R is a legitimate option. Option T Q O S P R is invalid since node P is visited after node S is visited.
9. In postorder traversal of binary tree right subtree is traversed before visiting root.
Explanation: Post-order method of traversing involves – i) Traverse left subtree in post-order, ii) Traverse right subtree in post-order, iii) visit the root.
10. What is the possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L when traversed in post-order.
Explanation: 5 binary trees are possible and they are,
11. A binary search tree contains values 7, 8, 13, 26, 35, 40, 70, 75. Which one of the following is a valid post-order sequence of the tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40 and 75?
A) 7, 8, 26, 13, 75, 40, 70, 35
B) 26, 13, 7, 8, 70, 75, 40, 35
C) 7, 8, 13, 26, 35, 40, 70, 75
D) 8, 7, 26, 13, 40, 75, 70, 35
Explanation: The binary tree contains values 7, 8, 13, 26, 35, 40, 70, 75. The given pre-order sequence is 35, 13, 7, 8, 26, 70, 40 and 75. So, the binary search tree formed is
Thus post-order sequence for the tree is 8, 7, 26, 13, 40, 75, 70 and 35.
The left subtree is traversed first, followed by the right subtree, and finally the current node in postorder traversal. S W T Q X U V R P is the posturer traversal of the tree. We know where the tree’s root node is. All elements before the root node belong to the left subtree, while those after the root belong to the right subtree. We will find all elements, store the nodes in the stack, and print the elements of the stack in this manner, resulting in preorder traversal.