Data Structures MultipleChoice Questions and Answers on Preorder Traversal

1. For the tree below, write the pre-order traversal.

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

Answer: a

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

2. For the tree below, write the post-order traversal.

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

Answer: c

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

3. 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) None of the mentioned

Answer: a

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

4. Select the code snippet which performs post-order traversal.

a)

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

b)

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

c)

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

d) None of the mentioned

Answer: a

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

5. 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) None of the mentioned

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. 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) None of the mentioned

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. What is the time complexity of pre-order traversal in the iterative fashion?

a) O(1)
b) O(n)
c) O(logn)
d) O(nlogn)

Answer: b

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

8. 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)

Answer: d

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

9. 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

Answer: b

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