Engineering Questions with Answers - Multiple Choice Questions

Data Structure MCQ – Preorder Traversal

1 - Question

For the tree below, write the pre-order traversal.
data-structure-questions-answers-preorder-traversal-q1
a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9

View Answer

Answer: a
Explanation: Pre order traversal follows NLR(Node-Left-Right).




2 - Question

 For the tree below, write the post-order traversal.
data-structure-questions-answers-preorder-traversal-q1
a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9

View Answer

Answer: c
Explanation: Post order traversal follows LRN(Left-Right-Node).




3 - Question

Select the code snippet which performs pre-order traversal.
a)

public void preorder(Tree root)
{
System.out.println(root.data);
	preorder(root.left);
	preorder(root.right);
}

b)

public void preorder(Tree root)
{
	preorder(root.left);
System.out.println(root.data);
	preorder(root.right);
}

c)

public void preorder(Tree root)
{
System.out.println(root.data);
	preorder(root.right);
	preorder(root.left);
}

d)

public void preorder(Tree root)
{
	preorder(root.right);
	preorder(root.left);
        System.out.println(root.data);
}
View Answer

Answer: a
Explanation: Pre-order traversal follows NLR(Node-Left-Right).




4 - Question

Select the code snippet that performs pre-order traversal iteratively.
a)

 

public void preOrder(Tree root)
{
        if (root == null) return;
	Stack<Tree> stk = new Stack<Tree>();
        st.add(root);
	while (!stk.empty())
        {
            Tree node = stk.pop();
            System.out.print(node.data + " ");
if (node.left != null) stk.push(node.left);
            if (node.right != null) stk.push(node.right);
        }
}

b)

public void preOrder(Tree root)
{
        if (root == null) return;
		Stack<Tree> stk = new Stack<Tree>();
	while (!stk.empty())
        {
            Tree node = stk.pop();
            System.out.print(node.data + " ");
            if (node.right != null) stk.push(node.right);
            if (node.left != null) stk.push(node.left);
        }
}

c)

public void preOrder(Tree root)
{
        if (root == null) return;
	Stack<Tree> stk = new Stack<Tree>();
        st.add(root);
	while (!stk.empty())
        {
            Tree node = stk.pop();
            System.out.print(node.data + " ");
            if (node.right != null) stk.push(node.right);
            if (node.left != null) stk.push(node.left);
        }
}

d)

public void preOrder(Tree root)
{
        if (root == null) return;
	Stack<Tree> stk = new Stack<Tree>();
        st.add(root);
	while (!stk.empty())
        {
            Tree node = stk.pop();
            System.out.print(node.data + " ");
            if (node.right != null) stk.push(node.left);
            if (node.left != null) stk.push(node.right);
        }
}
View Answer

Answer: b
Explanation: Post order traversal follows NLR(Left-Right-Node).




5 - Question

Select the code snippet that performs post-order traversal iteratively.
a)

 

public void postorder(Tree root)
{
        if (root == null)
        return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.left);
                stk.add(node);
                node = node.right;
            }
	    node = stk.pop();
	    if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

b)

public void postorder(Tree root)
{
        if (root == null)
        return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.right);
                stk.add(node);
                node = node.left;
            }
            node = stk.pop();
	    if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

c)

public void postorder(Tree root)
{
        if (root == null)
            return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.right);
                stk.add(node);
                node = node.left;
            }
	    node = stk.pop();
            if (node.right != null)
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

d)

public void postorder(Tree root)
{
        if (root == null)
            return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.left);
                stk.add(node);
                node = node.left;
            }
	    node = stk.pop();
            if (node.right != null)
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeLeft;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}
View Answer

Answer: c
Explanation: Add the root to the stack first, then continously check for the right and left children of the top-of-the-stack.




6 - Question

Select the code snippet that performs post-order traversal iteratively.
a)

 

public void postorder(Tree root)
{
        if (root == null)
        return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.left);
                stk.add(node);
                node = node.right;
            }
	    node = stk.pop();
	    if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

b)

public void postorder(Tree root)
{
        if (root == null)
        return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.right);
                stk.add(node);
                node = node.left;
            }
            node = stk.pop();
	    if (node.right != null && !stk.isEmpty() && node.right == stk.peek())
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

c)

public void postorder(Tree root)
{
        if (root == null)
            return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.right);
                stk.add(node);
                node = node.left;
            }
	    node = stk.pop();
            if (node.right != null)
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeRight;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}

d)

public void postorder(Tree root)
{
        if (root == null)
            return;
	Stack<Tree> stk = new Stack<Tree>();
        Tree node = root;
while (!stk.isEmpty() || node != null)
        {
            while (node != null)
            {
                if (node.right != null)
                    stk.add(node.left);
                stk.add(node);
                node = node.left;
            }
	    node = stk.pop();
            if (node.right != null)
            {
                Trees nodeRight = stk.pop();
                stk.push(node);
                node = nodeLeft;
            } else
            {
                System.out.print(node.data + " ");
                node = null;
            }
        }
}
View Answer

Answer: b
Explanation: The left and right children are added first to the stack, followed by the node, which is then popped. Post-order follows LRN policy.




7 - Question

What is the space complexity of the post-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)

View Answer

Answer: b
Explanation: Since you have to go through all the nodes, the complexity becomes O(n).




8 - Question

What is the space complexity of the post-order traversal in the recursive fashion? (d is the tree depth and n is the number of nodes)
a) O(1)
b) O(nlogd)
c) O(logd)
d) O(d)

View Answer

Answer: d
Explanation: In the worst case we have d stack frames in the recursive call, hence the complexity is O(d).




9 - Question

To obtain a prefix expression, which of the tree traversals is used?
a) Level-order traversal
b) Pre-order traversal
c) Post-order traversal
d) In-order traversal

View Answer

Answer: b
Explanation: As the name itself suggests, pre-order traversal can be used.




10 - Question

Consider the following data. The pre order traversal of a binary tree is A, B, E, C, D. The in order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is _________
a) A, C, D, B, E
b) A, B, C, D, E
c) A, B, C, E, D
d) D, B, E, A, C

View Answer

Answer: b
Explanation: The inorder sequence is B, E, A, D, C and Preorder sequence is A, B, E, C, D. The tree constructed with the inorder and preorder sequence is
data-structure-questions-answers-preorder-traversal-q10
The levelorder traversal (BFS traversal) is A, B, C, E, D.




11 - Question

Consider the following data and specify which one is Preorder Traversal Sequence, Inorder and Postorder sequences.
S1: N, M, P, O, Q
S2: N, P, Q, O, M
S3: M, N, O, P, Q
a) S1 is preorder, S2 is inorder and S3 is postorder
b) S1 is inorder, S2 is preorder and S3 is postorder
c) S1 is inorder, S2 is postorder and S3 is preorder
d) S1 is postorder, S2 is inorder and S3 is preorder

View Answer

Answer: c
Explanation: Preorder traversal starts from the root node and postorder and inorder starts from the left child node of the left subtree. The first node of S3 is different and for S1 and S2 it’s the same. Thus, S3 is preorder traversal and the root node is M. Postorder traversal visits the root node at last. S2 has the root node(M) at last that implies S2 is postorder traversal. S1 is inorder traversal as S2 is postorder traversal and S3 is preorder traversal. Therefore, S1 is inorder traversal, S2 is postorder traversal and S3 is preorder traversal.

Get weekly updates about new MCQs and other posts by joining 18000+ community of active learners