Trees come back in the Data Structures paper year after year, 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. Ten of the eleven questions here are GATE previous-year problems and the eleventh is a CoCubes placement question, each carrying its year. Work every answer out yourself before reading the explanation. For extra drilling on any of them, work through the Data Structures learn module. 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 other three statements hold, reading "complete" in (c) as this paper does, meaning every node has either zero or two children (see the full solution).
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. Count the edges two ways. Write n0 for the leaves, n1 for the nodes with one child and n2 for those with two, so the tree holds n0 + n1 + n2 nodes and therefore n0 + n1 + n2 − 1 edges. Counting those same edges downward from their parents gives n1 + 2n2 instead. Setting the two counts equal cancels n1 and collapses to n0 = n2 + 1, so with n leaves the degree-2 count is n − 1, whatever the shape (see the full solution).
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 full solution).
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 full solution).
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 full solution).
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, children 4 and 12, and grandchildren 2, 6, 10 and 14. Insertion order must place every node before its descendants, so the first value inserted is the root 8 and the second is 4 or 12. The third is then either the root's other child or a child of the one already placed, which leaves 2, 4, 6, 10, 12 and 14 as the only candidates; 5 is a leaf on the bottom level and can never appear that early (see the full solution).
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. For more drills on BST definitions, head to the Data Structures learn module.
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 full solution).
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 three all break at index 3: (a) hangs 12 under 6, (b) hangs 7 under 6, and (d) hangs 12 under 7 (see the full solution).
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 full solution).
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 full solution).
How trees are examined
GATE returns to trees along three predictable lines. 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.
