1. 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);
} Answer: a
Explanation:
Pre-order traversal follows NLR(Node-Left-Right).
2. 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)
public void postorder(Tree root)
{
postorder(root.right);
System.out.println(root.data);
postorder(root.left);
} Answer: b
Explanation:
Post order traversal follows NLR(Left-Right-Node).
3. Select the code snippet that performs pre-order traversal iteratively.
a)
public void preOrder(Tree root)
{
if (root == null) return;
Stack stk = new Stack();
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 stk = new Stack();
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 stk = new Stack();
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 stk = new Stack();
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);
}
} 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.
4. Select the code snippet that performs post-order traversal iteratively.
a)
public void postorder(Tree root)
{
if (root == null)
return;
Stack stk = new Stack();
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 stk = new Stack();
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 stk = new Stack();
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 stk = new Stack();
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;
}
}
} 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.
5. 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).
6. 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).
7. 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.
8. 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
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.
9. How many orders of traversal are applicable to a binary tree (In General)?
a) 1
b) 4
c) 2
d) 3
Answer: d
Explanation:
The three orders of traversal that can be applied to a binary tree are in-order, pre-order and post order traversal.
10. If binary trees are represented in arrays, what formula can be used to locate a left child, if the node has an index i?
a) 2i+1
b) 2i+2
c) 2i
d) 4i
Answer: a
Explanation:
If binary trees are represented in arrays, left children are located at indices 2i+1 and right children at 2i+2.
11. Using what formula can a parent node be located in an array?
a) (i+1)/2
b) (i-1)/2
c) i/2
d) 2i/2
Answer: b
Explanation:
If a binary tree is represented in an array, parent nodes are found at indices (i-1)/2.
12. Which of the following properties are obeyed by all three tree – traversals?
a) Left subtrees are visited before right subtrees
b) Right subtrees are visited before left subtrees
c) Root node is visited before left subtree
d) Root node is visited before right subtree
Answer: a
Explanation:
In preorder, inorder and postorder traversal the left subtrees are visited before the right subtrees. In Inorder traversal, the Left subtree is visited first then the Root node then the Right subtree. In postorder traversal, the Left subtree is visited first, then Right subtree and then the Root node is visited.
13. Which of the following is the predefined function for array reversal in javascript?
a) reverse()
b) arr_reverse()
c) array_reverse()
d) rev()
Answer: a
Explanation:
The predefined function for reversing an array is reverse() in javascript. It does not requires any argument.
14. Predefined function reverse() in C++ is available under which header file?
a) math
b) stdio
c) stdlib
d) algorithm
Answer: d
Explanation:
The predefined function for reversing an array is reverse() in C++ which comes under the library called an algorithm. It requires 2 arguments the first being the pointer to the starting index of the array and the second being the pointer to the last index of the array.
15. What is the time complexity of the juggling algorithm to rotate an array?
a) O(1)
b) O(n)
c) O(d)
d) O(n*d)
Answer: b
Explanation:
Time complexity of juggling algorithm is O(n). Its auxiliary space complexity is O(1).
16. Reversal algorithm and juggling algorithm for array rotation have the same time complexity.
a) True
b) False
Answer: a
Explanation:
Time complexity of juggling algorithm is O(n) which like that of reversal algorithm. They also have the same space complexity
