# 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)

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

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

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)

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>();
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>();
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

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

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

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

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