# Binary Trees MCQ

1. How many children does a binary tree have?

a) 2

b) any number of children

c) 0 or 1 or 2

d) 0 or 1

Answer: c

A binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child. A binary tree can have at most 2 nodes.

2. What is/are the disadvantages of implementing trees using normal arrays?

a) difficulty in knowing children nodes of a node

b) difficult in finding the parent of a node

c) have to know the maximum number of nodes possible before the creation of trees

d) difficult to implement

Answer: c

The size of the array is fixed in normal arrays. We need to know the number of nodes in the tree before array declaration. It is the main disadvantage of using arrays to represent binary trees.

3. What must be the ideal size of the array if the height of the tree is ‘l’?

a) 2l-1

b) l-1

c) l

d) 2l

Answer: a

Maximum elements in a tree (complete binary tree in the worst case) of height ‘L’ is 2L-1. Hence the size of the array is taken as 2L-1.

4. What are the children for node ‘w’ of a complete binary tree in an array representation?

a) 2w and 2w+1

b) 2+w and 2-w

c) w+1/2 and w/2

d) w-1/2 and w+1/2

Answer: a

The children for node ‘w’ of a complete binary tree in an array represent 2w and 2w+1.

The left child is generally taken as 2*w whereas the right child will be taken as 2*w+1 because the root node is present at index 0 in the array and to access every index position in the array.

5. What is the parent for a node ‘w’ of a complete binary tree in an array representation when w is not 0?

a) floor(w-1/2)

b) ceil(w-1/2)

c) w-1/2

d) w/2

Answer: a

The parent for a node ‘w’ of a complete binary tree in an array representation when w is not 0 is floor(w-1/2).

The floor of w-1/2 because we can’t miss a node.

6. If the tree is not a complete binary tree then what changes can be made for easy access to children of a node in the array?

a) every node stores data saying which of its children exist in the array

b) no need for any changes continue with 2w and 2w+1, if the node is at i

c) keep a separate table telling children of a node

d) use another array parallel to the array with a tree

Answer: a

The array cannot represent arbitrarily shaped trees. It can only be used in the case of complete trees. If every node stores data saying which of its children exists in the array then elements can be accessed easily.

8. Consider a situation of writing a binary tree into a file with memory storage efficiency in mind, is the array representation of the tree is good?

a) yes because we are overcoming the need for pointers and so space efficiency

b) yes because array values are indexable

c) No it is not efficient in the case of sparse trees and in remaining cases it is fine

d) No linked list representation of the tree is only fine

Answer: c

In the case of sparse trees (where one node per level in worst cases), the array size (2h)-1 where h is height but only h indexes will be filled and (2h)-1-h nodes will be left unused leading to space wastage.

9. Why is heap implemented using array representations than a tree(linked list) representations through both tree representations and heaps have the same complexities?

for binary heap -insert: O(log n) -delete min: O(log n) for a tree -insert: O(log n) -delete: O(log n)

Then why go with array representation when both are having same values?

a) arrays can store trees that are complete and heaps that are not complete

b) lists representation takes more memory hence memory efficiency is less and goes with arrays and arrays have better caching

c) lists have better caching

d) In lists insertion and deletion is difficult

Answer: b

In memory the pointer address for the next node may not be adjacent or nearer to each other and also array has wonderful caching power from os and manipulating pointers is an overhead. Heap data structure is always a complete binary tree.

10. Can a tree stored in an array using either one of inorder or post-order or pre-order traversals be again reformed?

a) Yes just traverse through the array and form the tree

b) No we need one more traversal to form a tree

c) No in the case of sparse trees

d) Yes by using both inorder and array elements

Answer: b

We need any two traversals for tree formation but if some additional stuff or techniques are used while storing a tree in an array then one traversal can facilitate like also storing null values of a node in an array.

1. Advantages of linked list representation of binary trees over arrays?

a) dynamic size

b) ease of insertion/deletion

c) ease in randomly accessing a node

d) both dynamic size and ease in insertion/deletion

Answer: d

The advantages of linked list representation of binary trees over arrays are that It has both dynamic size and ease in insertion and deletion as advantages.

2. Disadvantages of linked list representation of binary trees over arrays?

a) Randomly accessing is not possible

b) Extra memory for a pointer is needed with every element in the list

c) Difficulty in deletion

d) Random-access is not possible and extra memory with every element

Answer: d

The main disadvantages of linked list representation of binary trees over arrays is that Random access is not possible with linked lists.

3. Which of the following traversing algorithm is not used to traverse a tree?

a) Post order

b) Pre-order

c) Post order

d) Randomized

Answer: d

Generally all nodes in a tree are visited by using preorder, inorder, and postorder traversing algorithms.

4. Level order traversal of a tree is formed with the help of

a) breadth-first search

b) depth-first search

c) dijkstra’s algorithm

d) prims algorithm

Answer: a

- Level order traversal of a tree is formed with the help of breadth-first search.
- Level Order traversal is also known as Breadth-First Traversal since it traverses all the nodes at each level before going to the next level (depth).
- The last level of the tree is always equal to the height of the tree.

5. Identify the reason which doesn’t play a key role to use threaded binary trees?

a) The storage required by stack and queue is more

b) The pointers in most of the nodes of a binary tree are NULL

c) It is difficult to find a successor node

d) They occupy less size

Answer: d

Threaded binary trees are introduced to make the Inorder traversal faster without using any stack or recursion. Stack and Queue require more space and pointers in the majority of binary trees are null and difficulties are raised while finding successor nodes. Size constraints are not taken on threaded binary trees, but they occupy less space than a stack/queue.

6. The following lines talk about deleting a node in a binary tree. (the tree property must not be violated after deletion)

i) from root search for the node to be deleted

ii)

iii) delete the node at

what must be statement ii) and fill up statement iii)

a) ii)-find a random node, and replace it with a node to be deleted. iii)- delete the node

b) ii)-find the node to be deleted. iii)- delete the node at found location

c) ii)-find the deepest node, and replace it with the node to be deleted. iii)- delete a node

d) ii)-find the deepest node, and replace it with the node to be deleted. iii)- delete the deepest node

Answer: d

The following lines talk about deleting a node in a binary tree. (the tree property must not be violated after deletion)

i) from root search for the node to be deleted

ii) find the deepest node, and replace it with the node to be deleted.

iii) delete the deepest node

We just replace a to-be-deleted node with the last leaf node of a tree. this must not be done in case of BST or heaps.

7. What may be the psuedo code for finding the size of a tree?

a) find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node)

b) find_size(root_node–>left_node) + find_size(root_node–>right_node)

c) find_size(root_node–>right_node) – 1

d) find_size(root_node–>left_node + 1

Answer: a

The psuedo code for finding the size of a tree is to find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node)

Draw a tree and analyze the expression. we are always taking the size of the left subtree and right subtree and adding root value(1) to it and finally printing size.

8. What is missing in this logic of finding a path in the tree for a given sum (i.e checking whether there will be a path from roots to leaf nodes with a given sum)?

checkSum(struct bin-treenode *root , int sum) : if(root==null) return sum as 0 else : leftover_sum=sum-root_node-->value //missing

a) code for having recursive calls to either only left tree or right trees or both subtrees depending on their existence

b) code for having recursive calls to either only left tree or right trees

c) code for having recursive calls to either only left tree

d) code for having recursive calls to either only right trees

Answer: a

if(left subtree and right subtree) then move to both subtrees

else if only left subtree then move to left subtree carrying leftover_sum parameter

else if only the right subtree then moves to the right subtree carrying leftover_sum parameter.

9. What must be the missing logic below to print the mirror of a tree below as an example?

if(rootnode): mirror(rootnode-->left) mirror(rootnode-->right) //missing end

a) swapping of left and right nodes are missing

b) swapping of left with root nodes is missing

c) swapping of right with root nodes is missing

d) nothing is missing

Answer: a

The mirror is another tree with left and right children of nodes are interchanged as shown in the figure.

10. What is the code below trying to print?

void print(tree *root,tree *node) { if(root ==null) return 0 if(root-->left==node || root-->right==node) || print(root->left,node) ||printf(root->right,node) { print(root->data) } }

a) just printing all nodes

b) not a valid logic to do any task

c) printing ancestors of a node passed as an argument

d) printing nodes from a leaf node to a node passed as an argument

Answer: c

We are checking if the left or right node is what the argument sent or else if not the case then moves to a left node or right node and prints all nodes while searching for the argument node.

1. What is the maximum number of children that a binary tree node can have?

a) 0

b) 1

c) 2

d) 3

Answer: c

In a binary tree, a node can have atmost 2 nodes (i.e.) 0,1 or 2 left and right child.

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

Answer: a

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 the Right subtree, and then the Root node is visited.

3. A binary tree is a rooted tree but not an ordered tree.

a) true

b) false

Answer: b

A binary tree is a rooted tree and also an ordered tree (i.e) every node in a binary tree has at most two children.

4. How many common operations are performed in a binary tree?

a) 1

b) 2

c) 3

d) 4

Answer: c

Three common operations are performed in a binary tree- they are insertion, deletion, and traversal.

5. What is the traversal strategy used in the binary tree?

a) depth-first traversal

b) breadth-first traversal

c) random traversal

d) Priority traversal

Answer: b

Breadth-first traversal, also known as level order traversal is the traversal strategy used in a binary tree. It involves visiting all the nodes at a given level.

6. How many types of insertion are performed in a binary tree?

a) 1

b) 2

c) 3

d) 4

Answer: b

Two kinds of insertion operations are performed in a binary tree- inserting a leaf node and inserting an internal node.

7. 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

If a binary tree is represented in an array, parent nodes are found at indices (i-1)/2.

8. General ordered trees can be encoded into binary trees.

a) true

b) false

Answer: a

General ordered trees can be mapped into a binary tree by representing them in a left-child-right-sibling way.

9. How many bits would a succinct binary tree occupy?

a) n+O(n)

b) 2n+O(n)

c) n/2

d) n

Answer: b

A succinct binary tree occupies close to the minimum possible space established by lower bounds. A succinct binary tree would occupy 2n+O(n) bits.

10. The average depth of a binary tree is given as?

a) O(N)

b) O(√N)

c) O(N2)

d) O(log N)

Answer: d

The average depth of a binary tree is given as O(√N). In the case of a binary search tree, it is O(log N).

11. How many orders of traversal are applicable to a binary tree (In General)?

a) 1

b) 4

c) 2

d) 3

Answer: d

The three orders of traversal that can be applied to a binary tree are in-order, pre-order, and post-order traversal.

12. 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

If binary trees are represented in arrays, left children are located at indices 2i+1 and right children at 2i+2.

5. What is the time complexity of pre-order traversal in an iterative fashion?

a) O(1)

b) O(n)

c) O(logn)

d) O(nlogn)

Answer: b

The time complexity of pre-order traversal in an iterative fashion is O(n). 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

The space complexity of the post-order traversal in the recursive fashion is O(d). 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

To obtain a prefix expression Pre-order traversal tree traversals are used. As the name itself suggests, pre-order traversal can be used.

8. The pre-order traversal of a binary tree is A, B, E, C, D. The in-order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is _________

a) A, C, D, B, E

b) A, B, C, D, E

c) A, B, C, E, D

d) D, B, E, A, C

Answer: b

The pre-order traversal of a binary tree is A, B, E, C, D. The in-order traversal of the same binary tree is B, E, A, D, C. The level order sequence for the binary tree is A, B, C, D, E.

9. 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

Preorder traversal starts from the root node and postorder and inorder start 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 which 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.

1. In postorder traversal of binary tree right subtree is traversed before visiting root.

a) True

b) False

Answer: a

The Post-order method of traversing involves – i) Traverse left subtree in post-order, ii) Traverse right subtree in post-order, iii) visit the root.

2. What is the possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L when traversed in post-order.

a) 15

b) 3

c) 5

d) 8

Answer: c

The possible number of binary trees that can be created with 3 nodes, giving the sequence N, M, L when traversed in post-order is 5.

3. The post-order traversal of a binary tree is O P Q R S T. Then possible pre-order traversal will be ________

a) T Q R S O P

b) T O Q R P S

c) T Q O P S R

d) T Q O S P R

Answer: c

- The last, and second last nodes visited in post-order traversal are root and its right child respectively.
- Option T Q R S O P can’t be a pre-order traversal, because nodes O, and P are visited after the nodes Q, R, and S.
- Option T O Q R P S, can’t be valid, because the pre-order sequence given in option T O Q R P S and given post-order traversal creates a tree with node T as root and node O as a left subtree.
- Option T Q O P S R is valid. Option T Q O S P R is not valid as node P is visited after visiting node S.

4. A binary search tree contains values 7, 8, 13, 26, 35, 40, 70, and 75. Which one of the following is a valid post-order sequence of the tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40, and 75?

a) 7, 8, 26, 13, 75, 40, 70, 35

b) 26, 13, 7, 8, 70, 75, 40, 35

c) 7, 8, 13, 26, 35, 40, 70, 75

d) 8, 7, 26, 13, 40, 75, 70, 35

Answer: d

If a binary search tree contains values 7, 8, 13, 26, 35, 40, 70, and 75. Then the valid post-order sequence of the tree provided the pre-order sequence as 35, 13, 7, 8, 26, 70, 40, and 75 is 8, 7, 26, 13, 40, 75, 70, 35.

5. Which of the following pair’s traversals on a binary tree can build the tree uniquely?

a) post-order and pre-order

b) post-order and in-order

c) post-order and level order

d) level order and preorder

Answer: b

A binary tree can uniquely be created by post-order and in-order traversals.

6. A full binary tree can be generated using ______

a) post-order and pre-order traversal

b) pre-order traversal

c) post-order traversal

d) in-order traversal

Answer: a

Every node in a full binary tree has either 0 or 2 children. A binary tree can be generated by two traversals if one of them is in order. But, we can generate a full binary tree using post-order and pre-order traversals.

7. The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is ______

a) 3

b) 1

c) 2

d) any number

Answer: b

The maximum number of nodes in a tree for which post-order and pre-order traversals may be equal is 1. The tree with only one node has post-order and pre-order traversals equal.

8. The steps for finding post-order traversal are to traverse the right subtree, traverse the left subtree or visit the current node.

a) True

b) False

Answer: b

The left subtree is traversed first in post-order traversal, then the right subtree is traversed, and then the output current node.

9. The pre-order and in-order traversals of a binary tree are T M L N P O Q and L M N T O P Q. Which of the following is the post-order traversal of the tree?

a) L N M O Q P T

b) N M O P O L T

c) L M N O P Q T

d) O P L M N Q T

Answer: a

The pre-order and in-order are traversals of a binary tree are T M L N P O Q and L M N T O P Q. The post-order traversal of the tree is L N M O Q P T.

10. For a binary tree the first node visited in in-order and post-order traversal is the same.

a) True

b) False

Answer: b

For a binary tree, the first node visited in in-order and post-order traversal is the same.

5. What is the space complexity of the in-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

In the worst case, we have d stack frames in the recursive call, hence the complexity is O(d).

6. What is the time complexity of level order traversal?

a) O(1)

b) O(n)

c) O(logn)

d) O(nlogn)

Answer: b

The time complexity of level order traversal is O(n). Since you have to go through all the nodes, the complexity becomes O(n).

7. Which of the following graph traversals closely imitates level order traversal of a binary tree?

a) Depth First Search

b) Breadth-First Search

c) Depth & Breadth-First Search

d) Binary Search

Answer: b

Both level order tree traversal and breadth-first graph traversal follow the principle that visits your neighbors first and then moves on to further nodes.

8. In a binary search tree, which of the following traversals would print the numbers in ascending order?

a) Level-order traversal

b) Pre-order traversal

c) Post-order traversal

d) In-order traversal

Answer: d

In a binary search tree, a node’s left child is always lesser than the node and the right child is greater than the node, hence an in-order traversal would print them in a non-decreasing fashion.

1. The number of edges from the root to the node is called __________ of the tree.

a) Height

b) Depth

c) Length

d) Width

Answer: b

The number of edges from the root to the node is called the depth of the tree.

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

a) Height

b) Depth

c) Length

d) Width

Answer: a

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

3. What is a full binary tree?

a) Each node has exactly zero or two children

b) Each node has exactly two children

c) All the leaves are at the same level

d) Each node has exactly one or two children

Answer: a

A full binary tree is a tree in which each node has exactly 0 or 2 children.

4. What is a complete binary tree?

a) Each node has exactly zero or two children

b) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left

c) A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right

d) A tree In which all nodes have degree 2

Answer: c

A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right is called a complete binary tree. A Tree in which each node has exactly zero or two children is called a full binary tree. A Tree in which the degree of each node is 2 except leaf nodes is called a perfect binary tree.

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

a) h = O(loglogn)

b) h = O(nlogn)

c) h = O(n)

d) h = O(log n)

Answer: d

The nodes are either a part of the left subtree or the right subtree, so we don’t have to traverse all the nodes, this means the complexity is lesser than n, in the average case, assuming the nodes are spread evenly, the time complexity becomes O(long).

6. Which of the following is not an advantage of trees?

a) Hierarchical structure

b) Faster search

c) Router algorithms

d) Undo/Redo operations in a notepad

Answer: d

Undo/Redo operations in a notepad is an application of stack. Hierarchical structure, Faster search, and Router algorithms are advantages of trees.

7. In a full binary tree if the number of internal nodes is I, the number of leaves L is?

a) L = 2*I

b) L = I + 1

c) L = I – 1

d) L = 2*I – 1

Answer: b

The number of Leaf nodes in a full binary tree is equal to 1 + the Number of Internal Nodes i.e L = I + 1

8. In a full binary tree if the number of internal nodes is I, the number of nodes N is?

a) N = 2*I

b) N = I + 1

c) N = I – 1

d) N = 2*I + 1

Answer: d

In a full binary tree, the Relation between number of internal nodes(I) and nodes(N) is N = 2*I+1.

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

a) N = 2*L

b) N = L + 1

c) N = L – 1

d) N = 2*L – 1

Answer: d

The relation between the number of nodes(N) and leaves(L) is N=2*L-1.

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

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

b) Let T be a binary tree with λ levels. Then T has no more than 2λ – 1 nodes

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

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

Answer: d

In a binary tree, there are atmost 2k nodes in level k and 2k-1 total number of nodes. A number of levels are at least ceil(log(N+1)).

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

In order sequence of binary search, trees will always give ascending order of elements. The remaining all are true regarding binary search trees.

3. What is the specialty of the in-order 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 the priority of the node

Answer: b

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 increasing order.

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

The 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.

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

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.

1. What will be the height of a balanced full binary tree with 8 leaves?

a) 8

b) 5

c) 6

d) 4

Answer: d

A balanced full binary tree with l leaves has height h,

where h = log2l + 1.

So, the height of a balanced full binary tree with 8 leaves = log28 + 1 = 3 + 1 = 4.

2. The balance factor of a node in a binary tree is defined as _____

a) addition of heights of left and right subtrees

b) height of right subtree minus height of left subtree

c) height of left subtree minus height of right subtree

d) height of right subtree minus one

Answer: c

For a node in a binary tree, the difference between the heights of its left subtree and right subtree is known as the balance factor of the node.

3. AVL trees are more balanced than Red-black trees.

a) True

b) False

Answer: a

AVL tree is more balanced than a Red-black tree because the AVL tree has less height than the Red-black tree given that both trees have the same number of elements.

4. A binary tree is balanced if the difference between the left and right subtree of every node is not more than _______

a) 1

b) 3

c) 2

d) 0

Answer: a

A binary tree is balanced if the difference between the left and right subtree of every node is not more than 1

5. Which of the following tree data structures is not a balanced binary tree?

a) AVL tree

b) Red-black tree

c) Splay tree

d) B-tree

Answer: d

B-tree data structures is not a balanced binary tree. All the tree data structures given in the options are balanced, but B-tree can have more than two children.

7. Balanced binary tree with n items allows the lookup of an item in ________ worst-case time.

a) O(log n)

b) O(nlog 2)

c) O(n)

d) O(1)

Answer: a

Balanced binary tree with n items allows the lookup of an item in O(log n) worst-case time.

Searching an item in balanced binary is fast and the worst-case time complexity of the search is O(log n).

8. Which of the following data structures can be efficiently implemented using a height-balanced binary search tree?

a) sets

b) priority queue

c) heap

d) both sets and priority queue

Answer: d

A height-Balanced binary search tree can provide an efficient implementation of sets, and priority queues.

9. Two balanced binary trees are given with m and n elements respectively. They can be merged into a balanced binary search tree in _________ time.

a) O(m+n)

b) O(mn)

c) O(m)

d) O(mlog n)

Answer: a

First, we store the in-order traversals of both the trees in two separate arrays and then we can merge these sorted sequences in O(m+n) time. And then we construct the balanced tree from this final sorted array.

10. Which of the following is an advantage of the balanced binary search tree, like the AVL tree, compared to the binary heap?

a) insertion takes less time

b) deletion takes less time

c) searching takes less time

d) construction of the tree takes less time than a binary heap

Answer: a

Insertion and deletion, in both the binary heap and balanced binary search tree, take O(log n). But searching in a balanced binary search tree requires O(log n) while the binary heap takes O(n). Construction of a balanced binary search tree takes O(nlog n) time while binary heap takes O(n).

1. Which of the following is not the self-balancing binary search tree?

a) AVL Tree

b) 2-3-4 Tree

c) Red – Black Tree

d) Splay Tree

Answer: b

2-3-4 Tree is balanced search trees. But it is not a binary tree. So, it is not a self-balancing binary tree. AVL tree, Red-Black Tree, and Splay tree are self-balancing binary search trees.

2. The binary tree sort implemented using a self–balancing binary search tree takes ______ time in the worst case.

a) O(n log n)

b) O(n)

c) O(n^{2})

d) O(log n)

Answer: a

The worst-case running time of the binary tree sort is O(n^{2}). But, the worst-case running time can be improved to the O(n log n) using a self–balancing binary search tree.

3. An AVL tree is a self–balancing binary search tree, in which the heights of the two-child subtrees of any node differ by _________

a) At least one

b) At most one

c) Two

d) At most two

Answer: b

In an AVL tree, the difference between heights of the two-child subtrees of any node is at most one. If the height differs by more than one, the AVL tree performs rotations to balance the tree.

4. Associative arrays can be implemented using __________

a) B-tree

b) A doubly linked list

c) A single linked list

d) A self-balancing binary search tree

Answer: d

Associative arrays can be implemented using a self-balancing binary search tree as the worst-case time performance of self–balancing binary search trees is O(log n).

5. Self–balancing binary search trees have a much better average-case time complexity than hash tables.

a) True

b) False

Answer: b

For lookup, insertion and deletion hash table take O(1) time in average-case while self–balancing binary search trees takes O(log n). Therefore, hash tables perform better on average-case.

6. Which of the following is a self–balancing binary search tree?

a) 2-3 tree

b) Threaded binary tree

c) AA tree

d) Treap

Answer: c

An AA tree, which is a variation of the red-black tree, is a self–balancing binary search tree. 2-3 is the B-tree of order 3 and Treat is a randomized binary search tree. A threaded binary tree is not a balanced tree.

7. A self–balancing binary search tree can be used to implement ________

a) Priority queue

b) Hash table

c) Heap sort

d) Priority queue and Heap sort

Answer: a

Self-balancing binary search trees can be used to construct and maintain ordered lists, to achieve the optimal worst-case performance. So, self – a balancing binary search tree can be used to implement a priority queue, which is an ordered list.

8. In which of the following self–balancing binary search trees the recently accessed element can be accessed quickly?

a) AVL tree

b) AA tree

c) Splay tree

d) Red – Black tree

Answer: c

In a Splay tree, the recently accessed element can be accessed quickly. In the Splay tree, the frequently accessed nodes are moved towards the root so they are quick to access again.

9. The minimum height of a self-balancing binary search tree with n nodes is _____

a) log2(n)

b) n

c) 2n + 1

d) 2n – 1

Answer: a

The minimum height of a self-balancing binary search tree with n nodes is log2(n).

Self–balancing binary trees adjust the height by performing transformations on the tree at key insertion times, to keep the height proportional to log2(n).

10. Binary tree sort implemented using a self-balancing binary search tree takes O(n log n) time in the worst case but still it is slower than merge sort.

a) True

b) False

Answer: a

The worst-case performance of binary tree sort is O(n log n) when it is implemented using a self-balancing binary search tree. Self-balancing binary search trees perform transformations to balance the tree, which caused balancing overhead. Due to this overhead, binary tree sort is slower than merger sort.

1. Which of the following is not a random tree?

a) Treap

b) Random Binary Tree

c) Uniform Spanning Tree

d) AVL Tree

Answer: d

Treap, also known as a random binary search tree, Random binary tree, and Uniform spanning tree are all random trees. The random tree is a tree formed by a random process of addition and deletion of nodes. AVL tree is a self–balanced binary search tree.

2. Which process forms the randomized binary search tree?

a) Stochastic Process

b) Branching Process

c) Diffusion Process

d) Aggregation Process

Answer: a

The randomized binary search tree is formed by the stochastic process. The stochastic process or also called random process is a mathematical tool or object including random variables.

3. How many randomized binary search trees can be formed by the numbers (1, 3, 2)?

a) 2

b) 3

c) 6

d) 5

Answer: d

As there are 3 numbers (1, 3, 2) so a total of 6 combinations can be formed using three numbers but Since (2, 1, 3) and (2, 3, 1) are the same so in total there is 5 randomized binary search tree that can be formed.

4. What is the expected depth of a node in a randomized binary search tree?

a) log n

b) n!

c) n2

d) 2 log n + O(1)

Answer: d

The expected value of depth of a node that is for node a, the expected value of the length of the path from the root to node a is found to be at most 2 log n + O(1).

5. What is the longest length path for a node x in a random binary search tree for the insertion process?

a) log x

b) x^{2}

c) x!

d) 4.311 log x

Answer: d

Although it is difficult to find the length of the longest path in a randomized binary search tree, but it has been found that the longest length is around 4.311 log x.

6. What is the range of β in finding the length of the longest path in a randomized binary search tree?

a) (-1, 0)

b) (1, 0)

c) (0, 5)

d) (0, 1)

Answer: d

The longest path in a randomized binary search tree, but it has been found that the longest length is around 4.311 log x for node x. This is also equal to 1/β log x where β lies in the range (0, 1).

7. What is the expected number of leaves in a randomized binary search tree?

a) n + 1

b) (n + 1)/3

c) (n + 1)/2

d) n + 3

Answer: b

In a random mathematical model, the expected value of a number of leaves in a randomized binary search tree is found to be exactly (n + 1)/3 using probability.

8. Is Treap a randomized tree.

a) True

b) False

Answer: a

Treap is a type of data structure that is a combination of binary tree and heap. It is an example of a randomized binary search tree. It stores the value in pairs.

9. What is the probability of selecting a tree uniformly at random?

a) Equal to Catalan Number

b) Less Than Catalan Number

c) Greater than Catalan Number

d) Reciprocal of Catalan Number

Answer: d

A Catalan number is a sequence of a natural number that is used in counting problems. Hence it is found that selecting off a tree uniformly at random is reciprocal of the Catalan number.

10. Is a mathematical randomized tree that can be generated using beta distribution.

a) True

b) False

Answer: a

Beta distribution can be used using a different shape to generate a randomized binary search tree to create a special type of tree known as a botanical tree.

1. AA Trees are implemented using?

a) Colors

b) Levels

c) Node size

d) Heaps

Answer: b

AA Trees are implemented using levels instead of colors to overcome the disadvantages of Red-Black trees.

2. Which of the following is the correct definition for a horizontal link?

a) connection between the node and a child of equal levels

b) connection between two nodes

c) connection between two child nodes

d) connection between the root node and leaf node

Answer: a

A horizontal link is a connection between a node and a child of equal levels.

3. How will you remove a left horizontal link in an AA tree?

a) by performing right rotation

b) by performing left rotation

c) by deleting both the elements

d) by inserting a new element

Answer: a

A left horizontal link is removed by right rotation. A right horizontal link is removed by left rotation.

4. What are the two different operations done in an AA-Tree?

a) shift and color

b) skew and split

c) zig and zag

d) enqueue and dequeue

Answer: b

A skew removes a left horizontal link by right rotation and a split removes a right horizontal link by left rotation.

5. In an AA-tree, we process split first, followed by a skew.

a) True

b) False

Answer: b

An AA tree in computer science is a form of balanced tree used for storing and retrieving ordered data efficiently. In an AA tree, skew is processed first followed by a split.

6. How many different shapes do maintenance of AA-Tree need to consider?

a) 7

b) 5

c) 2

d) 3

Answer: c

An AA tree needs to consider only two shapes, unlike a red-black tree which needs to consider seven shapes of transformation.

7. What is the prime condition of the AA tree which makes it simpler than a red-black tree?

a) Only right children can be red

b) Only left children can be red

c) Right children should strictly be black

d) There should be no left children

Answer: a

The prime condition of AA-Tree is that only the right children can be red to eliminate possible restructuring cases.

8. Which of the following trees is similar to that of an AA tree?

a) Splay Tree

b) B+ Tree

c) AVL Tree

d) Red-Black Tree

Answer: d

AA- Tree is a small variation of the Red-Black tree. AA-Trees overcome the complexity faced in performing insertion and deletion in Red-Black Trees.

9. What is the worst-case analysis of an AA-Tree?

a) O(N)

b) O(log N)

c) O( N log N)

d) O(N2)

Answer: b

The worst-case analysis of an AA-Tree is mathematically found to be O(log N).

10. AA-Trees make more rotations than a red-black tree.

a) True

b) False

Answer: a

AA- trees make more rotations than a red-black tree since only two shapes are considered for an AA-Tree whereas seven shapes are considered in Red-Black trees.

11. Who is the inventor of AA-Tree?

a) Arne Anderson

b) Daniel Sleator

c) Rudolf Bayer

d) Jon Louis Bentley

Answer: a

AA-tree is invented by Arne Anderson. Daniel Sleator invented Splay Tree. Rudolf Bayer invented a Red-Black tree. Jon Louis Bentley invented the K-d tree.

12. What should be the condition for the level of a left node?

a) It should be less than or equal to that of its parent

b) It should be greater than that of its parent

c) It should be strictly less than that of its parent

d) The level should be equal to one

Answer: c

The level of a left node should be strictly less than that of its parent. The level of a right node is less than or equal to that of its parent.

13. Of the following rules that are followed by an AA-tree, which of the following is incorrect?

1- Only right children can be red

2- Procedures are coded recursively

3- Instead of storing colors, the level of a node is stored

4- There should not be any left children

a) 1

b) 2

c) 3

d) 4

Answer: d

In an AA-Tree, both left and right children can be present. The only condition is that only the right children can be red.

14. Comparing the speed of execution of Red-Black trees and AA-trees, which one has the faster search time?

a) AA-tree

b) Red-Black tree

c) Both have an equal search time

d) It depends

Answer: a

Since an AA tree tends to be flatter, the AA tree has a faster search time than a Red-Black tree.

1. What is an AVL tree?

a) a tree that is balanced and is a height-balanced tree

b) a tree that is unbalanced and is a height-balanced tree

c) a tree with three children

d) a tree with at most 3 children

Answer: a

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes. AVL tree is a self-balancing tree with a height difference atmost 1.

2. Why do we need a height-balanced binary tree?

a) to avoid the formation of skew trees

b) to save memory

c) to attain faster memory access

d) to simplify storing

Answer: a

In the real world dealing with random values is often not possible, the probability that u are dealing with non-random values(like sequential) leads to mostly skew trees, which leads to the worst case. hence we make height balance by rotations.

4. What is the maximum height of an AVL tree with p nodes?

a) p

b) log(p)

c) log(p)/2

d) p⁄2

Answer: b

Consider the height of the tree to be ‘he’, then a number of nodes which totals to p can be written in terms of height as N(he)=N(he-1)+1+N(he-2).

Since N(he) which is p can be written in terms of height as the beside recurrence relation which on solving gives N(he)= O(logp) as worst-case height.

5. To restore the AVL property after inserting an element, we start at the insertion point and move towards the root of that tree. is this statement true?

a) true

b) false

Answer: a

It is interesting to note that after insertion, only the path from that point to the node or only the subtrees are imbalanced in terms of height.

6. Given an empty AVL tree, how would you construct an AVL tree when a set of numbers are given without performing any rotations?

a) just build the tree with the given input

b) find the median of the set of elements given, make it a root, and construct the tree

c) use trial and error

d) use dynamic programming to build the tree

Answer: b

Sort the given input, find the median element among them, make it a root and construct left and right subtrees with elements lesser and greater than the median element recursively. this ensures the subtrees differ only by height 1.

7. What maximum difference in heights between the leafs of an AVL tree is possible?

a) log(n) where n is the number of nodes

b) n where n is the number of nodes

c) 0 or 1

d) atmost 1

Answer: a

At every level, we can form a tree with the difference in height between subtrees to be atmost 1 and so there can be log(n) such levels since the height of the AVL tree is log(n).

9. Consider the below left-left rotation pseudo-code where the node contains value pointers to left, and right child nodes, and a height value and the Height() function returns the height value stored at a particular node.

avltree leftrotation(avltreenode z): avltreenode w =x-left x-left=w-right w-right=x x-height=max(Height(x-left),Height(x-right))+1 w-height=max(missing)+1 return w What is missing? a) Height(w-left), x-height b) Height(w-right), x-height c) Height(w-left), x d) Height(w-left)

Answer: a

In the code, we are trying to make the left rotation and so we need to find the maximum of those two values.

10. Why to prefer red-black trees over AVL trees?

a) Because red-black is more rigidly balanced

b) AVL tree store balance factor in every node which costs space

c) AVL tree fails at scale

d) Red black is more efficient

Answer: b

Every node in an AVL tree needs to store the balance factor (-1, 0, 1) hence space costs to O(n), n being a number of nodes.

But in red-black, we can use the sign of the number (if numbers being stored are only positive) and hence save space for storing balancing information. there are even other reasons why redblack is mostly preferred.

1. What is a Cartesian tree?

a) a skip list in the form of a tree

b) a tree that obeys cartesian product

c) a tree that obeys heap property and whose inorder traversal yields the given sequence

d) a tree that obeys heap property only

Answer: c

A tree with heap property (parent is either small or big than children) and when traversed in inorder yields the given input sequence. refer to the diagram question for clarity.

2. Is the below tree representation of 50,100,400,300,280 the correct way to represent a cartesian tree?

a) true

b) false

Answer: a

A tree with heap property (parent is either small or big than children) and when traversed in inorder yields the given input sequence is called a cartesian tree. as the above figure satisfies both the properties. note that even a min-heap tree can be generated. the above is a max heap tree.

3. Which of the below statements are true?

i. Cartesian tree is not a height-balanced tree

ii. Cartesian tree of a sequence of unique numbers can be unique generated

a) both statements are true

b) only i. is true

c) only ii. is true

d) both are false

Answer: a

A height-balanced cartesian tree is not possible as seen in the above question. also any time a unique sequence possesses a unique cartesian tree, this can be proven through induction.

4. What is the specialty of cartesian sorting?

a) it sorts a partially sorted set of data quickly

b) it considers the cartesian product of elements

c) it sorts elements in less than O(logn)

d) it is a self-balancing tree

Answer: a

It can sort a set that requires only some sorting or displacements. for example consider 78, 79, 80, 82, 81, and 83, In this only 81 and 82 must be swapped to make it a complete sorted set, in this case, cartesian sort comes to the rescue.

5. Consider a sequence of numbers to have repetitions, how a cartesian tree can be constructed in such situations without violating any rules?

a) use any tie-breaking rule between repeated elements

b) cartesian tree is impossible when repetitions are present

c) construct a max heap in such cases

d) construct a min-heap in such cases

Answer: a

Consider any of the tie-breaking rules, for example, the element which appears first can be taken as small among the same elements and then apply cartesian tree rules.

6. What happens if we apply the below operations on an input sequence?

i. construct a cartesian tree for input sequence

ii. put the root element of the above tree in a priority queue

iii. if(the priority queue is not empty) then

iv. Search and delete the minimum value in priority queue

v. add that to output

vi. add cartesian tree children of the above node to priority queue

a) constructs a cartesian tree

b) sorts the input sequence

c) does nothing

d) produces some random output

Answer: b

The above-given steps are for sorting a cartesian tree. cartesian sort is beneficial in the case of a partially sorted set of elements. a cartesian sort can be considered as a selection or heap sort maintaining a priority queue.

7. Cartesian trees are most suitable for?

a) searching

b) finding nth element

c) minimum range query and lowest common ancestors

d) self-balancing a tree

Answer: c

In a cartesian tree minimum value can be found by finding the lowest common ancestor for the extreme elements. consider 11,9,19,16 the lowest element is 9 and is the lowest common ancestor for 11 and 16. and by applying a few techniques cartesian tree can be used to even find the lowest common ancestors efficiently.

These can be done in constant time. the tree can be constructed in linear time (this is the most efficient time for any tree construction) and takes space as many elements are there.

8. A treap is a cartesian tree with ___________

a) additional value, which is a priority value to the key generated randomly

b) additional value, which is a priority value to the key generated sequentially

c) additional heap rule

d) additional operations like removing a range of elements

Answer: a

A cartesian tree, if fed with a sorted sequence will generate a straight path (or in tree terminology a skew tree). moreover, a cartesian tree based on the same values from the search keys doesn’t work well. so a cartesian tree with a priority value in addition to the search key is called treap.

9. Cartesian trees solve range minimum query problems in constant time.

a) true

b) false

Answer: a

Range minimum query is finding the minimum element in a given subarray of an array. Constant time is achieved by storing the Cartesian trees for all the blocks in the array. Rmq’s are used in string matchings, computing the lowest common ancestor and longest common prefix of a sring.

10. Consider the below sequences.

array=60 90 10 100 40 150 90 reverse 2 to 3 array=60 10 90 100 40 150 90 reverse 3 to 6 array= 60 100 150 40 100 90 90 now printout from 1 to 6 :-- 60 100 150 40 100 90

How to achieve the above operation efficiently?

a) use linked lists

b) use AVL trees

c) use red-black trees

d) use traps (cartesian trees)

Answer: d

This can be solved efficiently using treap which is a modification of the cartesian tree. an attribute like “boolean reverse” can be maintained with every node representing whether to reverse or not.

1. What is a weight-balanced tree?

a) A binary tree that stores the sizes of subtrees in nodes

b) A binary tree with an additional attribute of weight

c) A height-balanced binary tree

d) A normal binary tree

Answer: a

Unlike AVL and red-black trees which uses height and color as bookkeeping information, weight-balanced trees use the size of subtrees.

2. What are the applications of weight balanced tree?

a) dynamic sets, dictionaries, sequences, maps

b) heaps

c) sorting

d) storing strings

Answer: a

They are a type of self-balancing trees that are mostly used in storing key-value pairs, which is mostly used in functional programming languages. they are very useful to maintain a big set of ordered objects.

3. A node of the weight-balanced tree has

a) key, left and right pointers, size

b) key, value

c) key, size

d) key

Answer: a

As a weight-balanced tree store the height of the subtrees, we need to use size as an additional attribute to every node. also value(for mappings) may be an optional attribute.

4. The size value of various nodes in a weight-balanced tree are leaf – zero internal node – the size of its two children is this true?

a) true

b) false

Answer: a

Size of a node k is size[k] = size[k.left] + 1 + size[k.right] and based on this the weight will be given as weight[k] = size[k] + 1.

5. What is the condition for a tree to be weight balanced. where a is factor and n is a node?

a) weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].

b) weight[n.left] >= a*weight[n.right] and weight[n.right] >= a*weight[n].

c) weight[n.left] >= a*weight[n.left] and weight[n.right] >= a*weight[n].

d) weight[n] is a non zero

Answer: a

The tree is said to be a-balanced if the condition is satisfied. and ‘a’ value will be determined during tree formation. a large value of ‘a’ is more effective.

6. What are the operations that can be performed on the weight-balanced tree?

a) all basic operations and set intersection, set union, and subset test

b) all basic operations

c) set intersection, set union, and subset test

d) only insertion and deletion

Answer: a

The specialty of a weight-balanced tree is a part of basic operations we can perform collective operations like set intersection, which helps in rapid prototyping in functional programming languages.

7. Consider a weight-balanced tree such that, the number of nodes in the left sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the farthest leaf) of such a tree on k nodes can be described as

a) log2 n

b) log4/3 n

c) log3 n

d) log3/2 n

Answer: d

Total number of nodes can be described by the recurrence T(n) = T((n-1)/3)) + T(2(n-1)/3) + 1 T(1) = 1. height of the tree will be H(n) = H(2/3(n-1)) + 1, H(1). drawing a recurrence tree and the cost at each level is 1 and the height will be log(3/2)n.

8. Why the below pseudo-code where x is a value, wt is the weight factor and t is the root node can’t inserted?

WeightBalanceTreeNode insert(int x, int wt, WeightBalanceTreeNode k) : if (k == null) k = new WeightBalanceTreeNode(x, wt, null, null) else if (x < t.element) : k.left = insert (x, wt, k.left) if (k.left.weight < k.weight) k = rotateWithRightChild (k) else if (x > t.element) : k.right = insert (x, wt, k.right) if (k.right.weight < k.weight) k = rotateWithLeftChild (k)

a) when x>t. element Rotate-with-left-child should take place and vice versa

b) the logic is incorrect

c) the condition for rotating children is wrong

d) insertion cannot be performed in weight-balanced trees

Answer: a

The rotations of children must be interchanged in the code.

9. What do the below definitions convey?

i. A binary tree is balanced if for every node it is gonna hold that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

ii. A binary tree is balanced if for any two leaves the difference of the depth is at most 1.

a) weight balanced and height balanced tree definitions

b) height-balanced and weight-balanced tree definitions

c) definitions of weight-balanced tree

d) definitions of height-balanced tree

Answer: a

They are the definitions of weight and height balanceness. height-balanced trees won’t convey weight balanceness but the opposite can be true.

10. Elements in a tree can be indexed by their position under the ordering of the keys and the ordinal position of an element can be determined, both with good efficiency.

a) true

b) false

Answer: a

In a weight-balanced tree, we can even store the key information to use as a key-value pair.

1. What is the special property of red-black trees and what root should always be?

a) a color which is either red or black and root should always be black color only

b) height of the tree

c) pointer to the next node

d) a color which is either green or black

Answer: a

An extra attribute which is the color red or black is used. the root is black because if it is red then one of the red-black tree properties which states that several black nodes from root to null nodes must be the same will be violated.

2. Why do we impose restrictions like

. root property is black . every leaf is black . children of red node are black . all leaves have same black

a) to get logarithm time complexity

b) to get linear time complexity

c) to get exponential time complexity

d) to get constant time complexity

Answer: a

We impose such restrictions to achieve self-balancing trees with logarithmic complexities for insertions, deletions, and searches.

4. What are the operations that could be performed in O(logn) time complexity by a red-black tree?

a) insertion, deletion, finding predecessor, successor

b) only insertion

c) only finding predecessor, successor

d) for sorting

Answer: a

We impose restrictions to achieve logarithm time complexities.

The impose restrictions are:

. root property is black

. every leaf is black

. children of a red node are black

. all leaves have the same black.

5. Which of the following is an application of Red-black trees and why?

a) used to store strings efficiently

b) used to store integers efficiently

c) can be used in process schedulers, maps, sets

d) for efficient sorting

Answer: c

RB tree is used for the Linux kernel in the form of a completely fair scheduler process scheduling algorithm. It is used for faster insertions and retrievals.

6. When it would be optimal to prefer Red-black trees over AVL trees?

a) when there are more insertions or deletions

b) when more search is needed

c) when the tree must be balanced

d) when log(nodes) time complexity is needed

Answer: a

Though both trees are balanced, when there are more insertions and deletions to make the tree balanced, AVL trees should have more rotations, it would be better to use red-black. but if more search is required AVL trees should be used.

7. Why Red-black trees are preferred over hash tables though hash tables have constant time complexity?

a) no they are not preferred

b) because of resizing issues of hash table and better ordering in red-black trees

c) because they can be implemented using trees

d) because they are balanced

Answer: b

Redblack trees have O(logn) for ordering elements in terms of finding the first and next elements. also whenever table size increases or decreases in the hash table you need to perform rehashing which can be very expensive in real-time.

Also red and black stores elements in sorted order rather than input order.

8. How can you save memory when storing color information in the Red-Black tree?

a) using the least significant bit of one of the pointers in the node for color information

b) using another array with colors of each node

c) storing color information in the node structure

d) using the negative and positive numbering

Answer: a

The node pointers can be used to store color with the help of significant bits. the exceptions of this method are in languages like java where pointers are not used this may not work.

9. When to choose the Red-Black tree, AVL tree, and B-trees?

a) many inserts, many searches, and when managing more items respectively

b) many searches, when managing more items respectively and many inserts respectively

c) sorting, sorting and retrieval respectively

d) retrieval, sorting and retrieval respectively

Answer: a

Red black when frequent inserts and deletes, AVL when less frequent inserts and deletes, B-tree when using paging from a slow storage device.

1. Which algorithm is used in the top tree data structure?

a) Divide and Conquer

b) Greedy

c) Backtracking

d) Branch

Answer: a

The top tree is a type of data structure that is based on an unrooted dynamic binary tree and is used to solve path-related problems. It allows an algorithm called divide and conquers.

2. For how many vertices in a set, is the top tree defined for an underlying tree?

a) 3

b) 4

c) 5

d) 2

Answer: d

The top tree is defined as a set having a maximum of 2 vertices for its underlying tree. Those sets having at maximum 2 vertices are called External Boundary Vertices.

3. How many edges are present in the path cluster?

a) 2

b) 3

c) 6

d) 1

Answer: a

There are at least 2 edges present in the path cluster. A cluster in the data structure is defined as the subtree that is connected having a maximum of 2 vertices known as Boundary Vertices.

4. How many edges does a leaf cluster contain?

a) 0

b) 1

c) 2

d) 3

Answer: a

If a cluster has no edges and contains only one vertex known as the boundary vertex then, it is known as a leaf cluster. So a leaf cluster doesn’t contain any edges. It is also known as a Point cluster.

5. How many edges are present in the Edge cluster?

a) 0

b) 1

c) 2

d) 4

Answer: b

A cluster containing only a single edge is known as an Edge cluster. So there are in total 1 edge present in the edge cluster. A cluster in the data structure is defined as the subtree that is connected having a maximum of 2 vertices known as Boundary Vertices.

6. Which data structure is used to maintain a dynamic forest using a link or cut operation?

a) Top Tree

b) Array

c) Linked List

d) Stack

Answer: a

The top tree data structure is used to maintain a dynamic forest using a link or cut operations. The top tree is a type of data structure that is based on an unrooted dynamic binary tree and is used to solve path-related problems.

7. If A ꓵ B (A and B are two clusters) is a singleton set then it is a Merge able cluster.

a) True

b) False

Answer: a

If A ꓵ B is a singleton set where A and B are two clusters, that is there is only one node that is common between the clusters then they are known as Mergeable clusters.

8. Is the Top tree used for maintaining a Dynamic set of trees called a forest.

a) True

b) False

Answer: a

The top tree data structure is used to maintain a dynamic forest using a link or cut operations. The top tree is a type of data structure that is based on an unrooted dynamic binary tree and is used to solve path-related problems.

9. What is the time complexity for the initialization of the top tree?

a) O (n)

b) O (n2)

c) O (log n)

d) O (n!)

Answer: a

Generally, trees have weight on their edges. Also, there is a one-to-one correspondence of the edges with the top trees. Therefore, top trees can be initialized in O (n) time.

10. How many top trees are there in a tree with a single vertex?

a) 0

b) 1

c) 2

d) 3

Answer: a

A tree having a single vertex has no clusters of trees present in the structure. Therefore, there are empty top trees in a tree having a single vertex. Trees with one node are single nodes.

11. Which property makes a top tree a binary tree?

a) Nodes as Cluster

b) Leaves as Edges

c) Root is Tree Itself

d) All of the mentioned

Answer: d

The top tree can be considered as a binary tree if the nodes form a cluster, leaves act as an edge and the root of the top tree acts as a tree itself. Then the top tree is called the binary tree.

12. Which of the dynamic operations are used in Top Tree data structure implementation?

a) Link

b) Cut

c) Expose

d) All of the mentioned

Answer: d

Link returns a single tree having different vertices from top trees. Cut removes the edge from the top three. Expose is used to implement queries on top trees. Hence all of the options are used as dynamic operations.

13. Which of the following are used as an internal operation in the Top tree?

a) Merge

b) Cut

c) Expose

d) Link

Answer: a

Link returns a single tree having different vertices from top trees. Cut removes the edge from the top tree. Expose is used to implement queries on top trees. While merge is an internal operation used to merge two clusters and return as a parent cluster.

14. What is the time complexity for maintaining a dynamic set of weighted trees?

a) O (n)

b) O (n2)

c) O (log n)

d) O (n!)

Answer: c

A lot of applications have been implemented using the Top tree interface. Maintaining a dynamic set of weighted trees is one such application that can be implemented with O (log n) time complexity.

1. What are splay trees?

a) self-adjusting binary search trees

b) self-adjusting binary trees

c) a tree with strings

d) a tree with probability distributions

Answer: a

Splay trees are height-balanced, self-adjusting BSTs.

2. Which of the following property of a splay tree is correct?

a) it holds probability usage of the respective subtrees

b) any sequence of j operations starting from an empty tree with h nodes atmost, takes O(jlogh) time complexity

c) sequence of operations with h nodes can take O(logh) time complexity

d) splay trees are unstable trees

Answer: b

This is a property of the splay tree that ensures faster access. we push the most recently used nodes to the top which leads to a faster access to recently used values.

3. Why to prefer splay trees?

a) easier to program

b) space efficiency

c) easier to program and faster access to recently accessed items

d) quick searching

Answer: c

Whenever you insert an element or remove or read an element that will be pushed or stored at the top which facilitates easier access or recently used stuff.

4. Is it true that splay trees have O(logn) amortized complexity?

a) true

b) false

Answer: a

We go with amortized time complexity when we feel that not all operations are worst and some can be efficiently done. in splay trees, not all splay operations will lead to O(logn) worst-case complexity.

5. What is a splay operation?

a) moving parent node to down of child

b) moving a node to root

c) moving root to leaf

d) removing leaf node

Answer: b

Splay trees mainly work using splay operations. whenever we insert, delete, and search for a node we splay the respective nodes to root. we have zig-zag and zig-zag operations.

6. Which of the following options is an application of splay trees?

a) cache Implementation

b) networks

c) send values

d) receive values

Answer: a

Splay trees can be used for faster access to recently accessed items and hence used for cache implementations.

7. When we have red-black trees and AVL trees that can perform most of the operations in logarithmic times, then what is the need for splay trees?

a) no there is no special usage

b) In real time it is estimated that 80% of access is only to 20% of data, hence most used ones must be easily available

c) redblack and avl are not upto mark

d) they are just another type of self-balancing binary search trees

Answer: b

Maybe the stats showing 80-20% may be not accurate, but in real-time that is the widely spread scenario seen. If you are into this type of situation, you must choose to implement splay trees.

10. What is the disadvantage of using splay trees?

a) height of a splay tree can be linear when accessing elements in non-decreasing order.

b) splay operations are difficult

c) no significant disadvantage

d) splay tree performs unnecessary splay when a node is only being read

Answer: a

The disadvantage of using splay trees is the height of a splay tree can be linear when accessing elements in non-decreasing order.

This will be the case after accessing all n elements in non-decreasing order. Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of an operation can be high. However, the amortized access cost of this worst-case is logarithmic O(log n).

1. What is the space complexity of a treap algorithm?

a) O(N)

b) O(log N)

c) O(log N)

d) O(N2)

Answer: a

The average case and worst-case space complexity of a treap are mathematically found to be O(N).

2. A treap is a combination of a tree and a heap.

a) false

b) true

Answer: a

A treap is a combination of a tree and a heap. The structure of a treap is determined by the fact that it is heap-ordered.

3. Which is the simplest of all binary search trees?

a) AVL tree

b) Treap

c) Splay tree

d) Binary heap

Answer: b

A treap is the simplest of all binary search trees. Each node is given a numeric priority and implementation is non-recursive.

4. What is the reason behind the simplicity of a treap?

a) Each node has data and a pointer

b) Each node is colored accordingly

c) It is a binary search tree following heap principles

d) Each node has a fixed priority field

Answer: d

A treap is the simplest of all because we don’t have to worry about adjusting the priority of a node.

5. What is the condition for the priority of a node in a treap?

a) a node’s priority should be greater than its parent

b) a node’s priority should be at least as large as its parent

c) the priority is randomly assigned and can have any value

d) a node’s priority is always given in decreasing order

Answer: b

A node’s priority should satisfy heap order. That is, any node’s priority should be at least as large as its parent.

6. Several other operations like union set difference and intersection can be done in traps.

a) True

b) False

Answer: a

Other than insertion, deletion, and search operations, several operations like union, intersection, and set difference can be done in traps.

7. What is the average running time of a treap?

a) O(N)

b) O(N log N)

c) O(log N)

d) O(M log N)

Answer: c

The average case and worst-case analysis of a treap are mathematically found to be O(log N).

8. Which node has the lowest priority in a treap?

a) root node

b) leaf node

c) null node

d) center node

Answer: a

A root node has the lowest priority in a treap since the node’s priority is based on heap order.

9. What is the priority of a null node?

a) 1

b) 0

c) random number

d) infinity

Answer: d

The priority of a null node is set to be infinity in a treap so that during deletion, the priority of that particular node is set to infinity, rotated, and freed.

10. Who invented treaps?

a) Cecilia and Raimund

b) Arne Andersson

c) Donald Shell

d) Harris and Ross

Answer: a

Cecilia and Raimund invented Treaps. Arne Andersson invented AA – Trees. Donald Shell invented shell sort and Harris and Ross formulated the maximum flow problem.

1. What is a threaded binary tree traversal?

a) a binary tree traversal using stacks

b) a binary tree traversal using queues

c) a binary tree traversal using stacks and queues

d) a binary tree traversal without using stacks and queues

Answer: d

A threaded binary tree traversal is a binary tree traversal without using stacks and queues. This type of tree traversal will not use stack or queue.

2. What are the disadvantages of normal binary tree traversals?

a) there are many pointers that are null and thus useless

b) there is no traversal that is efficient

c) complexity in implementing

d) improper traversals

Answer: a

The disadvantages of normal binary tree traversals is that there are many pointers that are null and thus useless. As there is the majority of pointers with null values go wasted we use threaded binary trees.

3. In general, the node content in a threaded binary tree is ________

a) leftchild_pointer, left_tag, data, right_tag, rightchild_pointer

b) leftchild_pointer, left_tag

c) leftchild_pointer, left_tag, right_tag, rightchild_pointer

d) leftchild_pointer, left_tag, data

Answer: a

In general, the node content in a threaded binary tree is leftchild_pointer, left_tag, data, right_tag, rightchild_pointer. It contains additional 2 pointers over the normal binary tree node structure.

4. What are null nodes filled within a threaded binary tree?

a) in order predecessor for left node and inorder successor for right node information

b) right node with inorder predecessor and left node with inorder successor information

c) they remain null

d) some other values randomly

Answer: a

The null nodes is filled within a threaded binary tree in order predecessor for left node and inorder successor for right node information.

If preorder or postorder is used then the respective predecessor and successor info is stored.

5. Which of the following tree traversals work if the null left pointer pointing to the predecessor and the null right pointer points to the successor in a binary tree?

a) inorder, postorder, preorder traversals

b) inorder

c) postorder

d) preorder

Answer: a

In threaded binary trees, the null left pointer points to the predecessor, and the right null pointer point to the successor. In threaded binary trees, we can use in-order, preorder, and postorder traversals to visit every node in the tree.

6. What are double and single-threaded trees?

a) when both left, and right nodes are having null pointers and the only right node is a null pointer respectively

b) having 2 and 1 node

c) using single and double-linked lists

d) using heaps and priority queues

Answer: a

The double and single-threaded trees is when both left, and right nodes are having null pointers and the only right node is a null pointer respectively.

They are properties of double and single-threaded binary trees respectively.

7. What is wrong with the below code for inorder traversal of inorder threaded binary tree:

inordertraversal(threadedtreenode root): threadedtreenode q = inorderpredecessor(root) while(q!=root): q=inorderpredecessor(q) print q.data

a) inordersuccessor instead of inorderpredecessor must be done

b) code is correct

c) it is code for post order

d) it is code for pre-order

Answer: a

Property of inorder threaded binary tree is left node with inorder predecessor and right node with inorder successor information are stored.

8. What is inefficient with the below-threaded binary tree picture?

a) it has dangling pointers

b) nothing inefficient

c) incorrect threaded tree

d) space is being used more

Answer: a

The nodes extreme left and right are pointing to nothing which could be also used efficiently.

1. Who developed the concept of the tango tree?

a) Erik Demaine

b) Mihai Patrascu

c) John Lacono

d) All of the mentioned

Answer: d

Erik Demaine is a well-known professor of Computer Science at MIT. John Lacono is an American computer scientist specializing in data structure and algorithm while Mihai Patrascu was a Romanian- American computer scientist. All of them together developed the concept of the Tango tree.

2. Which type of tree is a tango tree?

a) Ternary Tree

b) AVL Tree

c) Binary Search Tree

d) K-ary Tree

Answer: c

Tango tree is an example of a binary search tree that was developed by four famous scientists Erik Demaine, Mihai Patrascu, John Lacono, and Harmon in the year 2004.

3. After which city is the tango tree named?

a) Vatican City

b) Buenos Aires

c) New York

d) California

Answer: b

Tango is a popular couple dance or partner dance that was originated in the 1880s somewhere between Argentina and Uruguay. Buenos Aires is the capital city of Argentina. Hence they were named after Buenos Aires.

4. Which type of binary search tree or algorithm does the tango tree use?

a) Online

b) Offline

c) Static

d) Dynamic

Answer: d

A tango tree is an online binary search tree whose time complexity is O (log (log n)) when compared to the time complexity of the offline binary search tree model. Online algorithm processes input or data provided piece by piece.

5. What is the time complexity of achieving competitive ratio by tango tree?

a) O (log n)

b) O (n2)

c) O (n!)

d) O (log (log n))

Answer: d

A tango tree is an online binary search tree whose time complexity is O (log (log n)) when compared to the time complexity of the offline binary search tree model. Online algorithm processes input or data provided piece by piece.

6. Which type of binary search tree is imitated for the construction of a tango tree?

a) Complete Binary Search Tree

b) Perfect Binary Search Tree

c) Balanced Binary Search Tree

d) Degenerate Binary Search Tree

Answer: a

A tango tree is constructed by simulating a complete binary search tree. This tree is also known as the Reference tree, which contains all the elements of the tree. Also, the reference tree is never shown in actual implementation.

7. Which special balanced binary search tree is used to store the nodes of the auxiliary tree?

a) Red – Black Tree

b) Red – Brown Tree

c) Red – Yellow Tree

d) Red – Tango Tree

Answer: a

The path starting from the root and following the path of the preferred child node till the end of a leaf node is known as the preferred path. Nodes are stored in Red – The black tree for the representation of the preferred path.

8. Is the tango tree represented as a tree of trees.

a) True

b) False

Answer: a

The partitioning method is used by the tango tree which partitions a binary search tree into small sets of paths and then stores them in auxiliary trees. Hence tango tree is represented as a tree of trees.

9. Which operation is used to combine two auxiliary trees?

a) Join

b) Combinatorial

c) Add

d) Concatenation

Answer: a

If the top node of one of the reference trees amongst the two, is the child of the bottom node of the other reference tree, then the join operation can be carried out to join the two auxiliary trees.

10. Is the partitioning method used by Tango Tree.

a) True

b) False

Answer: a

The partitioning method is used by the tango tree which partitions a binary search tree into small sets of paths and then stores them in auxiliary trees. Hence tango tree is represented as a tree of trees.

11. Which operation is used to break a preferred path into two sets of parts at a particular node?

a) Differentiate

b) Cut

c) Integrate

d) Join

Answer: b

A preferred path is broken into two parts. One of them is known as the top part while the other is known as the bottom part. To break a preferred path into two sets, the cut operation is used at a particular node.

12. What is the upper bound for a tango tree if k is a number of interleaves?

a) k+2 O (log (log n))

b) k O (log n)

c) K2 O (log n)

d) k+1 O (log (log n))

Answer: d

The Upper bound is found to analyze the work done by a tango tree on a given set of sequences. In order to connect to the tango tree, the upper bound is found to be k+1 O (log (log n)).

13. What is the time complexity for searching k+1 auxiliary trees?

a) k+2 O (log (log n))

b) k+1 O (log n)

c) K+2 O (log n)

d) k+1 O (log (log n))

Answer: d

Since each search operation in the auxiliary tree takes O (log (log n)) time as auxiliary tree size is bounded by the height of the reference tree that is log n. So for k+1 auxiliary trees, the total search time is k+1 O (log (log n)).

14. What is the time complexity for the update cost on auxiliary trees?

a) O (log (log n))

b) k-1 O (log n)

c) K2 O (log n)

d) k+1 O (log (log n))

Answer: d

The update cost also is bounded by the upper bound. We perform one cut as well as one join operation for the auxiliary tree, so the total update cost for the auxiliary tree is found to be k+1 O (log (log n)).

15. Which of the following is the self-adjusting binary search tree?

a) AVL Tree

b) Splay Tree

c) Top Tree

d) Ternary Tree

Answer: b

A splay tree is a self–adjusting binary search tree. It performs basic operations on the tree-like insertion, deletion, and loop up performing all these operations in O (log n) time.

1. Which of the following is also known as Rope data structure?

a) Cord

b) String

c) Array

d) Linked List

Answer: a

The array is a linear data structure. Strings are a collection and sequence of codes, alphabets, or characters. A linked list is a linear data structure having a node containing data input and the address of the next node. The cord is also known as the rope data structure.

2. Which type of data structure does rope represent?

a) Array

b) Linked List

c) Queue

d) Binary Tree

Answer: d

The rope is a special binary tree in which the end nodes contain the string and its length. The array is a linear data structure. A linked list is a linear data structure having a node containing data input and the address of the next node. The queue is a data structure working on the principle of FIFO.

3. What is the time complexity for finding the node at x position where n is the length of the rope?

a) O (log n)

b) O (n!)

c) O (n2)

d) O (1)

Answer: a

In order to find the node at the x position in a rope data structure where N is the length of the rope, we start a recursive search from the root node. So the time complexity for the worst case is found to be O (log N).

4. What is the time complexity for creating a new node and then performing concatenation in the rope data structure?

a) O (log n)

b) O (n!)

c) O (n2)

d) O (1)

Answer: d

In order to perform the concatenation on the rope data structure, one can create two nodes S1 and S2, and then performing the operation in constant time that is the time complexity is O (1).

5. What is the time complexity for splitting the string into two new strings in the rope data structure?

a) O (n2)

b) O (n!)

c) O (log n)

d) O (1)

Answer: c

In order to perform the splitting on the rope data structure, one can split the given string into two new strings S1 and S2 in O (log n) time. So, the time complexity for the worst case is O (log n).

6. Which type of binary tree does rope require to perform basic operations?

a) Unbalanced

b) Balanced

c) Complete

d) Full

Answer: b

To perform the basic operations on a rope data structure like insertion, deletion, concatenation, and splitting, the rope should be a balanced tree. After performing the operations one should again re-balance the tree.

7. What is the time complexity for inserting the string and forming a new string in the rope data structure?

a) O (log n)

b) O (n!)

c) O (n2)

d) O (1)

Answer: a

In order to perform the insertion on the rope data structure, one can insert the given string at any position x to form a new string in O (log n) time.

So, the time complexity for the worst case is O (log n). This can be done by one split operation and two concatenation operations.

8. Is insertion and deletion operation faster in rope than in an array?

a) True

b) False

Answer: a

In order to perform the insertion on the rope data structure, the time complexity is O (log n).

In order to perform the deletion on the rope data structure, the time complexity for the worst case is O (log n). While for arrays the time complexity is O (n).

9. What is the time complexity for deleting the string to form a new string in the rope data structure?

a) O (n2)

b) O (n!)

c) O (log n)

d) O (1)

Answer: c

In order to perform the deletion on the rope data structure, one can delete the given string at any position x to form a new string in O (log n) time. So, the time complexity for the worst case is O (log n). This can be done by two split operations and one concatenation operation.

10. Is it possible to perform a split operation on a string in the rope if the split point is in the middle of the string.

a) True

b) False

Answer: a

In order to perform the splitting on the rope data structure, one can split the given string into two new strings S1 and S2 in O (log n) time.

So, the time complexity for the worst case is O (log n). The split operation can be performed if the split point is either at the end of the string or in the middle of the string.