Trees are the most heavily tested structure in the Data Structures paper, and the questions cluster tightly: counting nodes and edges, reconstructing a tree from traversals, tracing BST insertions, and reasoning about AVL heights and heap layouts. Below are 11 solved MCQs from KnowledgeGate's published question bank, almost all previous-year GATE problems with the year marked. Attempt each before the explanation, which is short by design. A note on the deep links: where a question is carried inside the course as a solved GATE PYQ, we link its exact page; one definitional question has no such page, so for that one the Data Structures learn module is your entry point. If the reasoning slips, the Binary Trees and Binary Search Trees deep dive rebuilds it end to end.
Binary tree basics and traversals
Q1. Which of the following statements is false? (GATE 1998)
(a) A tree with n nodes has n − 1 edges
(b) A labeled rooted binary tree can be uniquely constructed from its preorder and postorder traversals
(c) A complete binary tree with n internal nodes has n + 1 leaves
(d) The maximum number of nodes in a binary tree of height h is 2^(h+1) − 1
Answer: (b). Preorder and postorder alone cannot pin down a binary tree. For a root with a single child, preorder and postorder cannot tell whether that child is the left or the right one, so two different trees share both sequences. You need inorder as the third traversal to break the tie; the remaining three statements are all standard truths (see the solved page).
Q2. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is (GATE 1995)
(a) log₂ n
(b) n − 1
(c) n
(d) 2ⁿ
Answer: (b) n − 1. In any binary tree there is a fixed relationship between leaves and full nodes: the number of degree-2 nodes is always one less than the number of leaves. Every degree-2 node adds exactly one extra branch point, and a tree with n leaves needs n − 1 of them to fan out. So the count is n − 1, independent of the tree's shape (see the solved page).
Q3. A binary tree has root a; the children of a are b and e; the children of b are c and d; the left child of e is f; and the left child of c is g. Which sequence is its post-order traversal? (GATE 1996)
(a) f e g c d b a
(b) g c b d a f e
(c) g c d b f e a
(d) f e d g c b a
Answer: (c) g c d b f e a. Post-order visits left subtree, then right subtree, then root. Under b, the left child c first yields g then c, then the right child d, then b, giving g c d b. Under e, f comes before e, giving f e, and finally the root a is visited last, producing g c d b f e a (see the solved page).
Binary search tree operations
Q4. A binary search tree holds the values 1 to 8. It is traversed in pre-order and the values are printed. Which sequence is a valid output? (GATE 1997)
(a) 5 3 1 2 4 7 8 6
(b) 5 3 1 2 6 4 8 7
(c) 5 3 2 4 1 6 7 8
(d) 5 3 1 2 4 7 6 8
Answer: (d). In a BST pre-order, the first value is the root, then all smaller values (its left subtree) precede all larger ones (its right subtree), recursively. With root 5, the left group must be a valid BST pre-order over 1 to 4 and the right over 6 to 8. Only 5 3 1 2 4 7 6 8 keeps every subtree's values correctly partitioned around its local root (see the solved page).
Q5. A binary search tree is built by inserting, in order, 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. The number of nodes in the left and right subtrees of the root respectively is (GATE 1996)
(a) (4, 7)
(b) (7, 4)
(c) (8, 3)
(d) (3, 8)
Answer: (b) (7, 4). The first inserted value, 50, becomes the root and never moves. Every later value less than 50 lands in the left subtree and every value greater lands in the right, regardless of the internal shape. Counting the list, seven values are below 50 and four are above, giving (7, 4) (see the solved page).
Q6. Let P be the integers 1 to 15. For any insertion order that produces a complete binary search tree, which element can NEVER be the third element inserted? (GATE 2026)
(a) 4
(b) 2
(c) 10
(d) 5
Answer: (d) 5. A complete BST over 1 to 15 is the perfectly balanced tree with root 8 and children 4 and 12. The first insertion must be the root 8, and the second must be one of its children, 4 or 12. The third insertion has to be the other child, so it can only be 4 or 12; 5 sits deeper and can never appear that early (see the solved page).
Q7. What is a binary search tree? (CoCubes 2023)
(a) A tree in which each node has exactly two children
(b) A binary tree in which, for every node, all values in its left subtree are smaller and all values in its right subtree are greater
(c) A tree in which every node has at most two children and all children are leaves
(d) None of the above
Answer: (b). The defining rule of a BST is the ordering invariant applied at every node, not just the root: the entire left subtree is smaller and the entire right subtree is greater. Option (a) describes a full binary tree, and (c) describes a shallow shape with no ordering. Only (b) states the recursive search-tree property. This question has no separate solved page, so use the Data Structures learn module for its practice set.
Balanced trees and heaps
Q8. Which of the following is TRUE? (GATE 2008)
(a) The cost of searching an AVL tree is Θ(log n) but that of a binary search tree is O(n)
(b) The cost of searching an AVL tree is Θ(log n) but that of a complete binary tree is Θ(n log n)
(c) The cost of searching a binary search tree is O(log n) but that of an AVL tree is Θ(n)
(d) The cost of searching an AVL tree is Θ(n log n) but that of a binary search tree is O(n)
Answer: (a). An AVL tree keeps its height balanced, so its height is always Θ(log n) and search is guaranteed Θ(log n). A plain BST has no such guarantee: insert sorted keys and it degenerates into a chain of height n, making search O(n) in the worst case. That contrast is exactly what (a) states (see the solved page).
Q9. Which of the following arrays forms a heap? (GATE 2006)
(a) {23, 17, 14, 6, 13, 10, 1, 12, 7, 5}
(b) {23, 17, 14, 6, 13, 10, 1, 5, 7, 12}
(c) {23, 17, 14, 7, 13, 10, 1, 5, 6, 12}
(d) {23, 17, 14, 7, 13, 10, 1, 12, 5, 7}
Answer: (c). For a max-heap stored 0-indexed, each parent at index i must be at least as large as its children at 2i+1 and 2i+2. Checking (c), every parent dominates its children: 23 over 17 and 14, 17 over 7 and 13, 14 over 10 and 1, and so on down the array. The other options each violate the property at some parent, for example a child larger than its parent (see the solved page).
Q10. In a binary max-heap of n elements, the smallest element can be found in time (GATE 2006)
(a) O(n)
(b) O(log n)
(c) O(log log n)
(d) O(1)
Answer: (a) O(n). In a max-heap the largest element is at the root, but the smallest gives no such shortcut: it can only be a leaf, and there are about n/2 leaves spread across the bottom levels. There is no way to locate it without scanning all of them, so the minimum costs Θ(n). This asymmetry between finding the max and the min is a favourite trap (see the solved page).
Q11. What is the maximum height of an AVL tree with 7 nodes? Assume a single-node tree has height 0. (GATE 2009)
(a) 2
(b) 3
(c) 4
(d) 5
Answer: (b) 3. Find the tallest AVL tree that fits in 7 nodes using the minimum-node recurrence N(h) = 1 + N(h−1) + N(h−2), with N(0) = 1 and N(1) = 2. This gives N(2) = 4 and N(3) = 7, while N(4) = 12 exceeds 7. Since a height-3 AVL tree needs at least 7 nodes and that is exactly what we have, the maximum height is 3 (see the solved page).
How trees are examined
The set tracks how GATE keeps testing this topic. The basics block (Q1 to Q3) rewards the counting identities and the fact that preorder plus postorder is not enough to rebuild a tree. The BST block (Q4 to Q7) turns on one invariant applied recursively, so pre-order validity, subtree counts and legal insertion orders all fall out of "left smaller, right greater". The balanced and heap block (Q8 to Q11) is about worst-case guarantees: AVL height stays logarithmic, a max-heap hides its minimum among the leaves, and the AVL node recurrence bounds height precisely.
A missed question here is almost always a concept gap, not a practice-volume one. Rebuild the ideas through the GATE CS Exam category, then drill the full previous-year sets inside GATE Guidance by Sanchit Sir. Solve, review the ones you missed, and return to this set a week later; the second pass is where the marks get locked in.