Self Balancing Binary Search Tree Test

1. What is a full binary tree?

Each node has exactly zero or two children

Each node has exactly one or two children

All the leaves are at the same level

Each node has exactly two children

2. In a full binary tree if there are L leaves, then total number of nodes N are?

N = 2*L – 1

N = L – 1

N = L + 1

N = 2*L

3. Construct a binary search tree by using postorder sequence given below.
Postorder: 2, 4, 3, 7, 9, 8, 5.

Binary search tree by using postorder sequence postorder: 2, 4, 3, 7, 9, 8, 5 - option a

Binary search tree by using postorder sequence postorder: 2, 4, 3, 7, 9, 8, 5 - option d

Binary search tree by using postorder sequence postorder: 2, 4, 3, 7, 9, 8, 5 - option b

Binary search tree by using postorder sequence postorder: 2, 4, 3, 7, 9, 8, 5 - option c

4. Construct a binary tree using inorder and level order traversal given below.
Inorder Traversal: 3, 4, 2, 1, 5, 8, 9
Level Order Traversal: 1, 4, 5, 9, 8, 2, 3

Binary tree with traversal inorder Traversal: 3, 4, 2, 1, 5, 8, 9 - option c

Binary tree with traversal inorder Traversal: 3, 4, 2, 1, 5, 8, 9 - option d

Binary tree with traversal inorder Traversal: 3, 4, 2, 1, 5, 8, 9 - option a

Binary tree with traversal inorder Traversal: 3, 4, 2, 1, 5, 8, 9 - option b

5. Construct a binary tree by using postorder and inorder sequences given below.
Inorder: N, M, P, O, Q
Postorder: N, P, Q, O, M

A binary tree by using postorder & inorder sequences - option a

A binary tree by using postorder & inorder sequences - option c

A binary tree by using postorder & inorder sequences - option b

A binary tree by using postorder & inorder sequences - option d

6. What is the average case time complexity for finding the height of the binary tree?

h = O(n)

h = O(log n)

h = O(nlogn)

h = O(loglogn)

7. In a full binary tree if number of internal nodes is I, then number of nodes N are?

N = 2*I

N = I – 1

N = 2*I + 1

N = I + 1

8. The number of edges from the node to the deepest leaf is called _________ of the tree.

Length

Width

Height

Depth

9. In a full binary tree if number of internal nodes is I, then number of leaves L are?

L = I + 1

L = 2*I

L = 2*I – 1

L = I – 1

10. Which of the following is incorrect with respect to binary trees?

Let T be a binary tree with λ levels. Then T has no more than 2^{λ – 1} nodes

Let T be a binary tree with N nodes. Then the number of levels is at least ceil(log (N + 1))

Let T be a binary tree with N nodes. Then the number of levels is at least floor(log (N + 1))

Let T be a binary tree. For every k ≥ 0, there are no more than 2k nodes in level k