1. Which of the following is false about a binary search tree?
a) The left child is always lesser than its parent
b) The right child is always greater than its parent
c) The left and right sub-trees should also be binary search trees
d) In order sequence gives decreasing order of elements
Answer: d
Explanation:
In order sequence of binary search trees will always give ascending order of elements. Remaining all are true regarding binary search trees.
2. How to search for a key in a binary search tree?
a)
public Tree search(Tree root, int key)
{
if( root == null || root.key == key )
{
return root;
}
if( root.key < key )
{
return search(root.right,key);
}
else
return search(root.left,key);
}b)
public Tree search(Tree root, int key)
{
if( root == null || root.key == key )
{
return root;
}
if( root.key < key )
{
return search(root.left,key);
}
else
return search(root.right,key);
}c)
public Tree search(Tree root, int key)
{
if( root == null)
{
return root;
}
if( root.key < key )
{
return search(root.right,key);
}
else
return search(root.left,key);
}d)
public Tree search(Tree root, int key)
{
if( root == null)
{
return root;
}
if( root.key < key )
{
return search(root.right.right,key);
}
else
return search(root.left.left,key);
} Answer: a
Explanation:
As we know that the left child is lesser than the parent, if the root’s key is greater than the given key, we look only into the left sub-tree, similarly for right sub-tree.
3. What is the speciality about the inorder traversal of a binary search tree?
a) It traverses in a non increasing order
b) It traverses in an increasing order
c) It traverses in a random fashion
d) It traverses based on priority of the node
Answer: b
Explanation:
As a binary search tree consists of elements lesser than the node to the left and the ones greater than the node to the right, an inorder traversal will give the elements in an increasing order.
4. What does the following piece of code do?
public void func(Tree root)
{
func(root.left());
func(root.right());
System.out.println(root.data());
}
a) Preorder traversal
b) Inorder traversal
c) Postorder traversal
d) Level order traversal
Answer: c
Explanation:
In a postorder traversal, first the left child is visited, then the right child and finally the parent.
5. What does the following piece of code do?
public void func(Tree root)
{
System.out.println(root.data());
func(root.left());
func(root.right());
}
a) Preorder traversal
b) Inorder traversal
c) Postorder traversal
d) Level order traversal
Answer: a
Explanation:
In a preorder traversal, first the parent is visited, then the left child and finally the right child.
6. How will you find the minimum element in a binary search tree?
a)
public void min(Tree root)
{
while(root.left() != null)
{
root = root.left();
}
System.out.println(root.data());
}b)
public void min(Tree root)
{
while(root != null)
{
root = root.left();
}
System.out.println(root.data());
}c)
public void min(Tree root)
{
while(root.right() != null)
{
root = root.right();
}
System.out.println(root.data());
}d)
public void min(Tree root)
{
while(root != null)
{
root = root.right();
}
System.out.println(root.data());
} Answer: a
Explanation:
Since all the elements lesser than a given node will be towards the left, iterating to the leftmost leaf of the root will give the minimum element in a binary search tree.
7. How will you find the maximum element in a binary search tree?
a)
public void max(Tree root)
{
while(root.left() != null)
{
root = root.left();
}
System.out.println(root.data());
}b)
public void max(Tree root)
{
while(root != null)
{
root = root.left();
}
System.out.println(root.data());
}c)
public void max(Tree root)
{
while(root.right() != null)
{
root = root.right();
}
System.out.println(root.data());
}d)
public void max(Tree root)
{
while(root != null)
{
root = root.right();
}
System.out.println(root.data());
} Answer: c
Explanation:
Since all the elements greater than a given node are towards the right, iterating through the tree to the rightmost leaf of the root will give the maximum element in a binary search tree.
8. What are the worst case and average case complexities of a binary search tree?
a) O(n), O(n)
b) O(logn), O(logn)
c) O(logn), O(n)
d) O(n), O(logn)
Answer: d
Explanation:
Worst case arises when the tree is skewed(either to the left or right) in which case you have to process all the nodes of the tree giving O(n) complexity, otherwise O(logn) as you process only the left half or the right half of the tree.
9. Given that 2 elements are present in the tree, write a function to find the LCA(Least Common Ancestor) of the 2 elements.
a)
public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() > n2)
root = root.right();
else if (root.data() < n1 && root.data() < n2)
root = root.left();
else break;
}
System.out.println(root.data());
}b)
public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() < n2)
root = root.left();
else if (root.data() < n1 && root.data() > n2)
root = root.right();
else break;
}
System.out.println(root.data());
}c)
public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() > n2)
root = root.left();
else if (root.data() < n1 && root.data() < n2)
root = root.right();
else break;
}
System.out.println(root.data());
}d)
public void lca(Tree root,int n1, int n2)
{
while (root != NULL)
{
if (root.data() > n1 && root.data() > n2)
root = root.left.left();
else if (root.data() < n1 && root.data() < n2)
root = root.right.right();
else break;
}
System.out.println(root.data());
} Answer: c
Explanation:
The property of a binary search tree is that the lesser elements are to the left and greater elements are to the right, we use this property here and iterate through the tree such that we reach a point where the 2 elements are on 2 different sides of the node, this becomes the least common ancestor of the 2 given elements.
10. What are the conditions for an optimal binary search tree and what is its advantage?
a) The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost
b) You should know the frequency of access of the keys, improves the lookup time
c) The tree can be modified and you should know the number of elements in the tree before hand, it improves the deletion time
d) The tree should be just modified and improves the lookup time
Answer: a
Explanation:
For an optimal binary search The tree should not be modified and we need to find how often keys are accessed. Optimal binary search improves the lookup cost.
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
