Trees MCQs in Data Structures
๐ณ Trees โ 100 Tricky GATE MCQs with Detailed Solutions
1.
The maximum number of nodes in a binary tree of height h is:
A. 2^h
B. 2^(h+1) โ 1
C. hยฒ
D. 2^(hโ1) โ 1
Answer: B
Solution:
A full binary tree has 2^(h+1) โ 1 nodes (levels = h + 1). Example: height 2 โ 7 nodes.
2.
A binary tree with n nodes has exactly how many null pointers?
A. n
B. nโ1
C. n+1
D. 2n
Answer: C
Solution:
Each node contributes 2 links โ total 2n; nโ1 links used โ null = 2n โ (nโ1) = n + 1.
3.
In a full binary tree, if there are 15 leaf nodes, how many total nodes exist?
A. 29
B. 31
C. 30
D. 28
Answer: B
Solution:
Full binary tree: leaves = internal + 1 โ total = 2L โ 1 = 2(15) โ 1 = 31.
4.
A tree has 10 nodes of degree 2 and 5 nodes of degree 1. The number of leaf nodes = ?
A. 10
B. 5
C. 6
D. 11
Answer: B
Solution:
Degree 1 โ leaf nodes = 5 (nodes with no children).
5.
In a binary search tree (BST), in-order traversal yields:
A. Level order sequence
B. Random order
C. Sorted order
D. Reverse order
Answer: C
Solution:
In-order traversal โ Left, Root, Right โ sorted ascending sequence in BST.
6.
Which of the following traversals uses a queue?
A. Inorder
B. Preorder
C. Postorder
D. Level order
Answer: D
Solution:
Level-order uses BFS โ implemented using queue.
7.
A binary tree with 5 levels (root at level 0) has a maximum of:
A. 31 nodes
B. 32 nodes
C. 63 nodes
D. 15 nodes
Answer: A
Solution:
Max nodes = 2^(5) โ 1 = 31.
8.
The minimum number of nodes in a complete binary tree of height 3 is:
A. 8
B. 9
C. 7
D. 15
Answer: C
Solution:
Minimum occurs when last level partially filled โ min = 2^3 = 8? Actually, height 3 โ 7 minimum nodes.
9.
For a binary tree with 8 nodes, the number of possible binary trees = ?
A. 132
B. 1430
C. 429
D. 256
Answer: C
Solution:
Number of trees = Catalan(8) = (1/(8+1)) * (16 choose 8) = 1430 (for labeled). For unlabeled โ 429.
10.
A skewed binary tree behaves as:
A. Array
B. Queue
C. Linked list
D. Heap
Answer: C
Solution:
Skewed tree has one child per node โ similar to linked list.
11.
In a binary tree, if each non-leaf node has exactly 2 children, number of leaf nodes = internal + 1. True/False?
A. True
B. False
C. Only for full trees
D. Only for perfect trees
Answer: A
Solution:
Property of full binary tree โ L = I + 1.
12.
If a binary tree has 63 nodes, height of tree = ?
A. 5
B. 6
C. 7
D. 8
Answer: B
Solution:
2^(h+1) โ 1 = 63 โ h = 5.
13.
The number of edges in a tree with n vertices is:
A. n
B. nโ1
C. n+1
D. nยฒ
Answer: B
Solution:
Tree is minimally connected โ edges = vertices โ 1.
14.
Which of these traversals is non-recursive naturally?
A. Inorder
B. Preorder
C. Level order
D. Postorder
Answer: C
Solution:
Level-order โ queue โ non-recursive BFS traversal.
15.
A complete binary tree of height h has how many nodes?
A. Between 2^h and 2^(h+1)โ1
B. Exactly 2^h
C. 2^(h+1)โ1 only
D. hยฒ
Answer: A
Solution:
Complete tree fills all levels except last โ nodes โ [2^h, 2^(h+1)โ1].
16.
A binary tree with only right children has height = number of nodes โ 1. True?
A. True
B. False
C. Only for full trees
D. Only for even nodes
Answer: A
Solution:
Each node adds one level โ height = n โ 1.
17.
Which data structure is used for DFS traversal in a tree?
A. Queue
B. Stack
C. Linked List
D. Array
Answer: B
Solution:
DFS โ Stack (explicit or recursion).
18.
For a tree with 12 edges, total number of vertices = ?
A. 11
B. 12
C. 13
D. 14
Answer: C
Solution:
Vertices = edges + 1 = 13.
19.
Which traversal produces postfix expression from an expression tree?
A. Preorder
B. Inorder
C. Postorder
D. Level order
Answer: C
Solution:
Postorder โ L-R-Root โ postfix.
20.
A tree with 1 root and 6 leaf nodes must have at least:
A. 5 internal nodes
B. 6 internal nodes
C. 7 internal nodes
D. 4 internal nodes
Answer: A
Solution:
Full tree: L = I + 1 โ I = 6 โ 1 = 5.
21.
Which tree traversal can reconstruct a unique binary tree when combined with inorder traversal?
A. Preorder
B. Postorder
C. Level order
D. Either A or B
Answer: D
Solution:
Inorder + Preorder or Inorder + Postorder uniquely identifies a binary tree.
22.
Which of these is not a type of tree traversal?
A. Inorder
B. Outorder
C. Preorder
D. Postorder
Answer: B
Solution:
Outorder doesnโt exist; valid traversals are preorder, inorder, postorder.
23.
Which of the following binary trees is also a heap?
A. Complete & partially ordered
B. Full
C. Perfect
D. Skewed
Answer: A
Solution:
Heap = complete + heap order property.
24.
The number of binary trees possible with 3 nodes is:
A. 3
B. 4
C. 5
D. 6
Answer: C
Solution:
Catalan(3) = 5.
25.
A binary tree where every level, except possibly last, is full and all keys are as far left as possible is:
A. AVL tree
B. Complete tree
C. Full tree
D. Balanced tree
Answer: B
Solution:
Definition of complete binary tree.
26.
Which is true for a binary search tree (BST)?
A. Left < Root < Right B. Left > Root > Right
C. Root < All D. Root > All
Answer: A
Solution:
BST property: left subtree < root < right subtree.
27.
In a binary search tree, searching for an element is O(h). When h = logโn, BST is:
A. Balanced
B. Skewed
C. Complete
D. Degenerate
Answer: A
Solution:
Height = logโn โ balanced tree.
28.
AVL tree balances itself by:
A. Rotations
B. Swapping
C. Shuffling
D. Sorting
Answer: A
Solution:
AVL uses left/right rotations to maintain balance factor.
29.
Height of an empty tree = ?
A. -1
B. 0
C. 1
D. Undefined
Answer: A
Solution:
By definition, empty tree height = โ1; single node = 0.
30.
In a binary tree with 10 leaf nodes, how many nodes have 2 children?
A. 8
B. 9
C. 10
D. 11
Answer: A
Solution:
Full tree โ L = I + 1 โ I = 9; internal = 9, 2-child = I.
31.
Which traversal order of binary tree gives prefix expression?
A. Preorder
B. Inorder
C. Postorder
D. Level order
Answer: A
Solution:
Preorder โ root first โ prefix.
32.
For a tree having 15 nodes, the number of edges = ?
A. 15
B. 16
C. 14
D. 13
Answer: C
Solution:
Edges = n โ 1 = 14.
33.
Which property differentiates tree from graph?
A. No cycles
B. Directed edges
C. Nodes only
D. Equal edges and vertices
Answer: A
Solution:
Tree is acyclic connected graph.
34.
A tree has maximum degree 3. The maximum nodes at level 4 = ?
A. 81
B. 64
C. 27
D. 16
Answer: A
Solution:
Nodes = degree^level = 3โด = 81.
35.
Which of these is not a binary tree variant?
A. Threaded tree
B. AVL tree
C. Heap
D. Spanning tree
Answer: D
Solution:
Spanning tree is a graph concept.
36.
Which node has no parent in any tree?
A. Leaf
B. Root
C. Internal node
D. Child
Answer: B
Solution:
Root = topmost โ no parent.
37.
Height of complete binary tree with n nodes โ ?
A. logโ(n+1) โ 1
B. n
C. โn
D. 2n
Answer: A
Solution:
Height = floor(logโn).
38.
Which traversal visits nodes in sorted order for a BST?
A. Inorder
B. Preorder
C. Level order
D. Postorder
Answer: A
Solution:
Inorder โ ascending sequence.
39.
In BST, the smallest element is located at:
A. Leftmost node
B. Rightmost node
C. Root
D. None
Answer: A
Solution:
Minimum = leftmost.
40.
What is the number of leaf nodes in a perfect binary tree of height 4?
A. 8
B. 15
C. 16
D. 31
Answer: C
Solution:
Leaves = 2^h = 2โด = 16.
41.
If a binary tree has 20 leaf nodes, how many internal nodes will it have in a full binary tree?
A. 18
B. 19
C. 20
D. 21
Answer: B
Solution:
In a full binary tree, L = I + 1 โ I = 20 โ 1 = 19.
42.
The height of a perfect binary tree containing 127 nodes is:
A. 6
B. 7
C. 8
D. 9
Answer: B
Solution:
2^(h+1) โ 1 = 127 โ h = 6.
43.
Which traversal gives postfix expression from an expression tree?
A. Preorder
B. Inorder
C. Postorder
D. Level order
Answer: C
Solution:
Postorder traversal (LeftโRightโRoot) generates postfix form.
44.
In a max heap, every parent node is:
A. Smaller than its children
B. Greater than or equal to its children
C. Equal to its children
D. Unrelated to its children
Answer: B
Solution:
Max heap property ensures each parent โฅ its children.
45.
In a complete binary tree with 31 nodes, number of leaf nodes = ?
A. 15
B. 16
C. 14
D. 10
Answer: B
Solution:
Leaf nodes in perfect binary tree = 2^h = 16 for h=4 (31 = 2โตโ1).
46.
If the height of an AVL tree is h, minimum number of nodes = ?
A. 2^h โ 1
B. F(h+2) โ 1
C. 2^(h+1) โ 1
D. hยฒ
Answer: B
Solution:
AVL minimum nodes = F(h+2) โ 1 (Fibonacci relation).
47.
In BST, which operation requires O(h) time complexity?
A. Traversal
B. Insertion
C. Building tree
D. Printing
Answer: B
Solution:
Insertion/search both take O(h) (height of tree).
48.
Which of the following is not a balanced binary tree?
A. AVL tree
B. Red-Black tree
C. Splay tree
D. Binary search tree
Answer: D
Solution:
BST may be skewed โ not necessarily balanced.
49.
The number of distinct binary trees possible with 4 nodes = ?
A. 14
B. 16
C. 24
D. 12
Answer: A
Solution:
Catalan(4) = (1/5) ร (8 choose 4) = 14.
50.
For a binary tree with n internal nodes, the number of null links = ?
A. n
B. n+1
C. 2n
D. nโ1
Answer: B
Solution:
Total links = 2n, used = nโ1, so null = 2n โ (nโ1) = n+1.
51.
The maximum number of nodes at level i in a binary tree = ?
A. 2^i
B. iยฒ
C. iร2
D. 2^(iโ1)
Answer: A
Solution:
Level i (root at 0): maximum 2^i nodes.
52.
In an AVL tree, balance factor is defined as:
A. |height(left) โ height(right)|
B. height(left) + height(right)
C. height(left) โ height(right)
D. None
Answer: C
Solution:
BF = height(left) โ height(right).
53.
An AVL tree has balance factor values only in:
A. {0,1}
B. {โ1,0,1}
C. {โ2,โ1,0,1,2}
D. Any integer
Answer: B
Solution:
AVL allows balance factor in {โ1, 0, +1}.
54.
A binary tree with n nodes has exactly (nโ1) edges.
A. True
B. False
Answer: A
Solution:
Every node except root has one incoming edge โ nโ1 edges.
55.
In-order traversal of BST gives:
A. Descending order
B. Ascending order
C. Random
D. Level-wise order
Answer: B
Solution:
BST inorder โ sorted ascending order.
56.
In a heap represented as array, left child of node at index i is stored at:
A. 2i
B. 2i + 1
C. i/2
D. 2i โ 1
Answer: B
Solution:
For 0-based indexing: left child = 2i + 1, right = 2i + 2.
57.
In a heap, the parent of a node at index i is:
A. i/2
B. (iโ1)/2
C. 2i
D. 2i+1
Answer: B
Solution:
Parent = floor((iโ1)/2).
58.
Which of the following trees is used in priority queue implementation?
A. AVL tree
B. Heap
C. Red-Black tree
D. Splay tree
Answer: B
Solution:
Heaps are used for priority queues.
59.
A full binary tree with 7 levels has total nodes = ?
A. 63
B. 127
C. 255
D. 511
Answer: B
Solution:
2โท โ 1 = 127.
60.
In a BST, which node has the greatest key value?
A. Root
B. Rightmost
C. Leftmost
D. Any
Answer: B
Solution:
Rightmost node holds maximum value.
61.
If a node has degree 3, it can have maximum how many children?
A. 2
B. 3
C. 4
D. 1
Answer: B
Solution:
Degree = number of children โ max = 3.
62.
Number of possible labeled trees with 4 vertices = ?
A. 16
B. 64
C. 256
D. 4^(4โ2)
Answer: D
Solution:
Cayleyโs formula: n^(nโ2) = 4ยฒ = 16.
63.
For a B-tree of order 4, each node can have at most:
A. 3 keys
B. 4 keys
C. 5 keys
D. 6 keys
Answer: A
Solution:
Order m โ max keys = m โ 1 = 3.
64.
Minimum degree (t) of a B-tree of order m = ?
A. m/2
B. mโ1
C. 2m
D. โm
Answer: A
Solution:
t = ceil(m/2).
65.
In a binary tree, number of nodes of degree 2 is one less than number of leaf nodes.
A. True
B. False
Answer: A
Solution:
For full binary trees, L = I + 1.
66.
Which traversal can be used to reconstruct a unique binary tree if postorder is also known?
A. Inorder
B. Preorder
C. Level order
D. None
Answer: A
Solution:
Inorder + Postorder โ unique tree.
67.
In a threaded binary tree, null pointers are replaced by:
A. Stack pointers
B. Inorder predecessor/successor
C. Random pointers
D. Links to parent
Answer: B
Solution:
Threads link to inorder predecessor/successor.
68.
In-order traversal of threaded binary tree is faster because:
A. Uses recursion
B. Uses queue
C. No recursion/stack needed
D. Uses DFS
Answer: C
Solution:
Thread links eliminate recursion/stack.
69.
Which tree stores variable-length codes efficiently?
A. Binary search tree
B. Huffman tree
C. B-tree
D. AVL tree
Answer: B
Solution:
Huffman tree used for optimal variable-length encoding.
70.
In Huffman tree, higher frequency characters are placed:
A. At leaves
B. Near the root
C. At rightmost
D. Randomly
Answer: B
Solution:
Higher frequency โ shorter codes โ closer to root.
71.
In a Red-Black tree, root is always:
A. Red
B. Black
C. Any
D. Depends on rotation
Answer: B
Solution:
Root must always be black.
72.
Which property holds for every Red-Black tree?
A. Every path has same number of black nodes
B. No two red nodes adjacent
C. Root is black
D. All of the above
Answer: D
Solution:
All three are defining Red-Black properties.
73.
Maximum number of rotations needed in AVL insertion = ?
A. 1
B. 2
C. 3
D. 4
Answer: B
Solution:
At most 2 rotations (double rotation).
74.
Which rotation is required for Left-Right imbalance?
A. LL rotation
B. RR rotation
C. LR rotation
D. RL rotation
Answer: C
Solution:
Left-Right imbalance โ LR rotation.
75.
Which rotation fixes a Right-Right imbalance in AVL?
A. Left rotation
B. Right rotation
C. Double rotation
D. No rotation
Answer: A
Solution:
RR โ single left rotation.
76.
If height of AVL = 10, maximum nodes possible โ ?
A. 2047
B. 1000
C. 512
D. 1023
Answer: D
Solution:
Perfect tree upper bound โ 2^(h+1)โ1 = 2047, AVL slightly less, โ1023.
77.
A heap allows which operations efficiently?
A. Insert and Find-Max/Min
B. Search any element
C. Delete arbitrary node
D. Sorting directly
Answer: A
Solution:
Heaps optimize insert + extract-min/max.
78.
Number of edges in a complete binary tree with n nodes = ?
A. n
B. nโ1
C. log n
D. n/2
Answer: B
Solution:
Tree with n nodes โ nโ1 edges.
79.
In a heap of 31 nodes, number of leaf nodes = ?
A. 16
B. 15
C. 14
D. 12
Answer: A
Solution:
For n nodes โ โn/2โ leaves = 16.
80.
In a binary tree, number of internal nodes with degree 2 = 20, degree 1 = 10, then leaf nodes = ?
A. 31
B. 11
C. 21
D. 9
Answer: B
Solution:
Total = I2 + I1 + L = N; L = I2 + 1 = 21? But degree1 adds one less link. So total leaves = 11.
81.
A perfect binary tree of height h has number of leaf nodes = ?
A. h
B. 2^h
C. 2^(h+1)
D. hยฒ
Answer: B
Solution:
Leaves = 2^h.
82.
For a binary tree, if in-order and postorder traversals are known, we can find:
A. Only leaf nodes
B. Only root
C. Complete tree
D. Height
Answer: C
Solution:
Inorder + Postorder uniquely reconstructs binary tree.
83.
Which of the following is a height-balanced tree?
A. AVL tree
B. Heap
C. Binary search tree
D. Threaded tree
Answer: A
Solution:
AVL tree maintains height balance property.
84.
For n keys, the height of a complete binary search tree โ ?
A. logโ(n)
B. n
C. n/2
D. nยฒ
Answer: A
Solution:
Balanced tree height = logโ(n).
85.
For a tree with 40 nodes, number of edges = ?
A. 40
B. 39
C. 41
D. 20
Answer: B
Solution:
Always nโ1 = 39 edges.
86.
Which tree is most suitable for dictionary implementation?
A. AVL tree
B. Red-Black tree
C. Binary search tree
D. B-tree
Answer: D
Solution:
B-trees used in databases & dictionaries.
87.
In a B+ tree, all values are stored:
A. In internal nodes
B. In leaf nodes
C. Randomly
D. Both internal & leaves
Answer: B
Solution:
All actual data stored in leaf nodes.
88.
Which of the following trees is used in file indexing?
A. B-tree
B. Binary tree
C. Heap
D. Trie
Answer: A
Solution:
B-trees used for file indexing (disk access optimized).
89.
In a Trie, each edge represents:
A. Word
B. Character
C. Node
D. String
Answer: B
Solution:
Each edge โ one character of stored string.
90.
The number of null links in a binary tree with n nodes = ?
A. n+1
B. 2n
C. nโ1
D. n
Answer: A
Solution:
Each node contributes 2 links โ null = n+1.
91.
In-order traversal of BST yields ascending order, while reverse in-order gives:
A. Ascending order
B. Descending order
C. Random
D. Same as preorder
Answer: B
Solution:
Reverse inorder โ right-root-left โ descending.
92.
The diameter of a tree is:
A. Maximum distance between two leaves
B. Number of edges in longest path
C. Both A & B
D. None
Answer: C
Solution:
Diameter = longest path length (leaf-to-leaf).
93.
Height-balanced tree ensures:
A. O(log n) search
B. O(n) search
C. O(n log n) insertion
D. Constant search
Answer: A
Solution:
Balance ensures logarithmic search time.
94.
Which data structure can represent arithmetic expression hierarchy?
A. Stack
B. Tree
C. Queue
D. Array
Answer: B
Solution:
Expression trees model operator precedence.
95.
Heap sort is based on which tree property?
A. Binary search
B. Heap order
C. Level order
D. Postorder
Answer: B
Solution:
Heap sort relies on heap order property.
96.
Number of internal nodes in a perfect binary tree with 63 nodes = ?
A. 31
B. 32
C. 33
D. 30
Answer: B
Solution:
Leaves = 32, internal = leavesโ1 = 31; total 63 โ 31 internal.
97.
In binary search tree, deleting a node with two children requires:
A. Removing left child
B. Replacing with inorder successor/predecessor
C. Deleting entire subtree
D. Random replacement
Answer: B
Solution:
BST deletion (two children) โ replace with inorder successor or predecessor.
98.
In a heap, insertion requires:
A. O(1) time
B. O(log n) time
C. O(n) time
D. O(n log n)
Answer: B
Solution:
Insertion โ bubble-up operation = O(log n).
99.
Which traversal order of binary tree can be obtained using a stack?
A. Preorder
B. Inorder
C. Postorder
D. All of these
Answer: D
Solution:
All DFS traversals can be implemented using stack.
100.
Which of the following statements about trees is false?
A. Every tree is a connected graph
B. Every tree is acyclic
C. Every acyclic graph is a tree
D. Tree with n nodes has (nโ1) edges
Answer: C
Solution:
Every tree is acyclic & connected, but not every acyclic graph is a tree (can be disconnected).
About the Author
