1.
What is the time complexity of pre-order traversal in the iterative fashion?
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.
Answer: Option 'C'
Post order traversal follows LRN(Left-Right-Node).
3.
Select the code snippet which performs post-order traversal.
public void postorder(Tree root)
{
System.out.println(root.data);
postorder(root.left);
postorder(root.right);
}
public void postorder(Tree root)
{
postorder(root.left);
postorder(root.right);
System.out.println(root.data);
}
public void postorder(Tree root)
{
System.out.println(root.data);
postorder(root.right);
postorder(root.left);
}
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)
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.
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);
}
}
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);
}
}
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);
}
}
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.
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;
}
}
}
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;
}
}
}
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;
}
}
}
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.
Answer: Option 'A'
Pre order traversal follows NLR(Node-Left-Right).
8.
Select the code snippet which performs pre-order traversal.
public void preorder(Tree root)
{
System.out.println(root.data);
preorder(root.left);
preorder(root.right);
}
public void preorder(Tree root)
{
preorder(root.left);
System.out.println(root.data);
preorder(root.right);
}
public void preorder(Tree root)
{
System.out.println(root.data);
preorder(root.right);
preorder(root.left);
}
Answer: Option 'A'
Pre-order traversal follows NLR(Node-Left-Right).
9.
To obtain a prefix expression, which of the tree traversals is used?
Answer: Option 'B'
As the name itself suggests, pre-order traversal can be used.