# 500+ Binary Trees MCQs with FREE PDF

These 500+ Binary Trees MCQs with FREE PDF contains Questions and Answers on binary trees using arrays and linked lists, preorder, postorder and inorder traversal, avl tree, binary tree properties and operations, cartesian tree, weight balanced tree, red black and splay trees, threaded binary tree and binary search trees, aa tree, top tree, treap, tango tree and rope. We have the best collection of Binary Trees MCQs and answer with FREE PDF. These Binary Trees MCQs will help you to prepare for any competitive exams like: BCA, MCA, GATE, GRE, IES, PSC, UGC NET, DOEACC Exams at all levels – you just have to practice regularly.

## Binary Trees MCQs

#### 1. 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: Random access is not possible and extra memory with every element

a) Post order

b) Pre order

c) Post order

d) Randomized

#### 3. The following lines talks 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 random node,replace with node to be deleted. iii)- delete the node

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

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

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

Answer: ii)-find deepest node,replace with node to be deleted. iii)- delete the deepest node

#### 4. 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: find_size(root_node–>left_node) + 1 + find_size(root_node–>right_node)

50+ Binary Trees using Array MCQs with FREE PDF

a) 1

b) 2

c) 3

d) 4

a) n+O(n)

b) 2n+O(n)

c) n/2

d) n

a) O(N)

b) O(√N)

c) O(N2)

d) O(log N)

a) 1

b) 4

c) 2

d) 3

a) 2i+1

b) 2i+2

c) 2i

d) 4i

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

a) 0

b) 1

c) 2

d) 3

50+ Binary Trees using Linked Lists MCQs with FREE PDF

a) O(1)

b) O(nlogd)

c) O(logd)

d) O(d)

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

#### 13. Consider the following data. 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: A, B, C, E, D

#### 14. 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: S1 is inorder, S2 is postorder and S3 is preorder

50+ Binary Tree Operations MCQs with FREE PDF

a) 15

b) 3

c) 5

d) 8

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

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

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

a) 3

b) 1

c) 2

d) any number

a) True

b) False

#### 21. 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. Which of following is 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

50+ Preorder Traversal MCQs with FREE PDF

a) O(1)

b) O(n)

c) O(logn)

d) O(nlogn)

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

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

a) Level-order traversal

b) Pre-order traversal

c) Post-order traversal

d) In-order traversal

50+ Postorder Traversal MCQs with FREE PDF

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

a) L = 2*I

b) L = I + 1

c) L = I – 1

d) L = 2*I – 1

Answer: L = I + 1

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

a) N = 2*I

b) N = I + 1

c) N = I – 1

d) N = 2*I + 1

Answer: N = 2*I + 1

#### 27. 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: A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right

a) Height

b) Depth

c) Length

d) Width

a) Height

b) Depth

c) Length

d) Width

#### 30. 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: Each node has exactly zero or two children

#### 31. 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: h = O(log n)

50+ Inorder Traversal MCQs with FREE PDF

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

#### 33. 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: In order sequence gives decreasing order of elements

50+ Binary Tree Properties MCQs with FREE PDF

a) 1

b) 3

c) 2

d) 0

a) 8

b) 5

c) 6

d) 4

#### 36. 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: height of left subtree minus height of right subtree

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

#### 38. Which of the following data structures can be efficiently implemented using height balanced binary search tree?

a) sets

b) priority queue

c) heap

d) both sets and priority queue

Answer: both sets and priority queue

a) O(m+n)

b) O(mn)

c) O(m)

d) O(mlog n)

#### 40. Which of the following is an advantage of balanced binary search tree, like AVL tree, compared to 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 binary heap

Answer: insertion takes less time

50+ Binary Search Tree MCQs with FREE PDF

a) log2(n)

b) n

c) 2n + 1

d) 2n – 1

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

a) O(n log n)

b) O(n)

c) O(n2)

d) O(log n)

a) At least one

b) At most one

c) Two

d) At most two

a) True

b) False

a) True

b) False

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

a) 2-3 tree

b) Threaded binary tree

c) AA tree

d) Treap

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

50+ Balanced Binary Tree MCQs with FREE PDF

a) n + 1

b) (n + 1)/3

c) (n + 1)/2

d) n + 3

#### 50. Which of the following is not a random tree?

a) Treap

b) Random Binary Tree

c) Uniform Spanning Tree

d) AVL Tree

#### 51. Which process forms the randomized binary search tree?

a) Stochastic Process

b) Branching Process

c) Diffusion Process

d) Aggregation Process

a) 2

b) 3

c) 6

d) 5

a) True

b) False

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

a) True

b) False

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

a) log x

b) x2

c) x!

d) 4.311 log x

50+ Self Balancing Binary Search Tree MCQs with FREE PDF

a) Colors

b) Levels

c) Node size

d) Heaps

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

a) connection between node and a child of equal levels

b) connection between two nodes

c) connection between two child nodes

d) connection between root node and leaf node

a) O(N)

b) O(log N)

c) O( N log N)

d) O(N2)

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

50+ Randomized Binary Search Tree MCQs with FREE PDF

#### 61. What is an AVL tree?

a) a tree which is balanced and is a height balanced tree

b) a tree which is unbalanced and is a height balanced tree

c) a tree with three children

d) a tree with atmost 3 children

Answer: a tree which is balanced and is a height balanced tree

#### 62. Why we need to a binary tree which is height balanced?

a) to avoid formation of skew trees

b) to save memory

c) to attain faster memory access

d) to simplify storing

Answer: to avoid formation of skew trees

#### 63. 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: AVL tree store balance factor in every node which costs space

a) true

b) false

#### 65. Given an empty AVL tree, how would you construct 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 as root and construct the tree

c) use trial and error

d) use dynamic programming to build the tree

Answer: find the median of the set of elements given, make it as root and construct the tree

50+ AA Tree MCQs with FREE PDF

#### 66. What is a Cartesian tree?

a) a skip list in the form of tree

b) a tree which obeys cartesian product

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

d) a tree which obeys heap property only

Answer: a tree which obeys heap property and whose inorder traversal yields the given sequence

#### 67. 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: use any tie-breaking rule between repeated elements

#### 68. 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 above tree in a priority queue

iii. if( priority queue is not empty) then

iv. search and delete minimum value in priority queue

v. add that to output

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

a) constructs a cartesian tree

b) sorts the input sequence

c) does nothing

d) produces some random output

Answer: sorts the input sequence

#### 69. 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: both statements are true

#### 70. 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: minimum range query and lowest common ancestors

50+ AVL Tree MCQs with FREE PDF

#### 71. 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: weight[n.left] >= a*weight[n] and weight[n.right] >= a*weight[n].

#### 72. What are the operations that can be performed on 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: all basic operations and set intersection, set union and subset test

#### 73. 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 binary tree that stores the sizes of subtrees in nodes

#### 74. What are the applications of weight balanced tree?

a) dynamic sets, dictionaries, sequences, maps

b) heaps

c) sorting

d) storing strings

Answer: dynamic sets, dictionaries, sequences, maps

#### 75. A node of the weight balanced tree has

a) key, left and right pointers, size

b) key, value

c) key, size

d) key

Answer: key, left and right pointers, size

50+ Cartesian Tree MCQs with FREE PDF

#### 76. 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: can be used in process schedulers, maps, sets

#### 77. 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 tree must be balanced

d) when log(nodes) time complexity is needed

Answer: when there are more insertions or deletions

#### 78. 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 redblack trees

c) because they can be implemented using trees

d) because they are balanced

Answer: because of resizing issues of hash table and better ordering in redblack trees

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

a) using 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 negative and positive numbering

Answer: using least significant bit of one of the pointers in the node for color information

#### 80. 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 next node

d) a color which is either green or black

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

50+ Weight Balanced Tree MCQs with FREE PDF

a) 0

b) 1

c) 2

d) 4

a) Top Tree

b) Array

d) Stack

a) O (n)

b) O (n2)

c) O (log n)

d) O (n!)

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

a) Divide and Conquer

b) Greedy

c) Backtracking

d) Branch

Answer: Divide and Conquer

a) 3

b) 4

c) 5

d) 2

a) 2

b) 3

c) 6

d) 1

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

a) 0

b) 1

c) 2

d) 3

50+ Red Black Tree MCQs with FREE PDF

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

a) cache Implementation

b) networks

c) send values

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

#### 90. Which of the following property of splay tree is correct?

a) it holds probability usage of the respective sub trees

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

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

#### 92. When we have red-black trees and AVL trees that can perform most of 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% access is only to 20% 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

50+ Top Tree MCQs with FREE PDF

a) AVL tree

b) Treap

c) Splay tree

d) Binary heap

#### 94. What is the condition for 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: a node’s priority should be at least as large as its parent

a) True

b) False

a) O(N)

b) O(N log N)

c) O(log N)

d) O(M log N)

a) root node

b) leaf node

c) null node

d) centre node

a) 1

b) 0

c) random number

d) infinity

#### 99. Who invented treaps?

a) Cecilia and Raimund

c) Donald Shell

d) Harris and Ross

Answer: Cecilia and Raimund

50+ Splay Tree MCQs with FREE PDF

a) O(N)

b) O(log N)

c) O(log N)

d) O(N2)

a) false

b) true

a) AVL tree

b) Treap

c) Splay tree

d) Binary heap

#### 103. What is the condition for 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: a node’s priority should be at least as large as its parent

a) True

b) False

a) O(N)

b) O(N log N)

c) O(log N)

d) O(M log N)

#### 106. Which node has the lowest priority in a treap?

a) root node

b) leaf node

c) null node

d) centre node

50+ Treap MCQs with FREE PDF

#### 107. Who developed the concept of tango tree?

a) Erik Demaine

b) Mihai Patrascu

c) John Lacono

d) All of the mentioned

Answer: All of the mentioned

#### 108. Which type of tree is tango tree?

a) Ternary Tree

b) AVL Tree

c) Binary Search Tree

d) K-ary Tree

Answer: Binary Search Tree

a) Vatican City

b) Buenos Aires

c) New York

d) California

#### 110. Which type of binary search tree is imitated for construction of tango tree?

a) Complete Binary Search Tree

b) Perfect Binary Search Tree

c) Balanced Binary Search Tree

d) Degenerate Binary Search Tree

Answer: Complete Binary Search Tree

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

a) Red – Black Tree

b) Red – Brown Tree

c) Red – Yellow Tree

d) Red – Tango Tree

Answer: Red – Black Tree

#### 112. 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: k+1 O (log (log n))

#### 113. Which operation is used to combine two auxiliary trees?

a) Join

b) Combinatorial

d) Concatenation

50+ Threaded Binary Tree MCQs with FREE PDF

a) Cord

b) String

c) Array

a) Array

c) Queue

d) Binary Tree

#### 116. 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: O (log n)

a) Unbalanced

b) Balanced

c) Complete

d) Full

#### 118. 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: O (log n)

a) True

b) False

#### 120. 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: O (log n)

50+ Tango Tree MCQs with FREE PDF

a) Cord

b) String

c) Array

a) Array

c) Queue

d) Binary Tree

#### 123. 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: O (log n)

a) Unbalanced

b) Balanced

c) Complete

d) Full

#### 125. 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: O (log n)

a) True

b) False

#### 127. 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: O (log n)

50+ Rope MCQs with FREE PDF