How many bits would a succinct binary tree occupy?
a) n+O(n)
b) 2n+O(n)
c) n/2
d) n
Explanation: A succinct binary tree occupies close to minimum possible space established by lower bounds. A succinct binary tree would occupy 2n+O(n) bits.
The average depth of a binary tree is given as?
a) O(N)
b) O(√N)
c) O(N2)
d) O(log N)
Explanation: The average depth of a binary tree is given as O(√N). In case of a binary search tree, it is O(log N).
How many orders of traversal are applicable to a binary tree (In General)?
a) 1
b) 4
c) 2
d) 3
Explanation: The three orders of traversal that can be applied to a binary tree are in-order, pre-order and post order traversal.
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
Explanation: If binary trees are represented in arrays, left children are located at indices 2i+1 and right children at 2i+2.
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
Explanation: If a binary tree is represented in an array, parent nodes are found at indices (i-1)/2.
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
