Preorder Traversal | Data Structure MCQs

1.

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: Option 'B'

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

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: Option 'C'

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

3.

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 these

Answer: Option 'A'

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

4.

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: Option 'D'

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

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 these

Answer: Option 'C'

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 these

Answer: Option ''

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.

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: Option 'A'

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

8.

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 these

Answer: Option 'A'

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

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: Option 'B'

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

Preorder Traversal | Data Structure MCQs Download Pdf