Question types seen repeatedly in past papers. More stars means more frequent.
★★★
Traversal of a given tree / BST built from keys
Insert keys in order, then write postorder or inorder; or find which sequence is a valid preorder of a BST.
★★★
Node counting (n₀ = n₂ + 1, full k-ary tree)
Leaves of a tree with given internal-node counts.
★★★
Height / number of nodes in a balanced or AVL tree
Maximum height of an AVL tree with n nodes, minimum nodes for a given height.
★★★
BST delete / insert result
Predict the shape after deletes using the inorder successor.
★★★
Number of BSTs / binary trees
Catalan numbers, sometimes with constraints on height.
Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
15 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
15 questions · 0 correct of 0 attempted · marks 0 / 21
Year:
GATE 2025 CS2 · Q13MCQ1 mark
Consider a binary tree T in which every node has either zero or two children. Let n > 0 be the number of nodes in T. Which ONE of the following is the number of nodes in T that have exactly two children?
GATE 2025 CS1 · Q26MSQ1 mark
Which of the following statement(s) is/are TRUE for any binary search tree (BST) having n distinct integers?
One or more options may be correct. Select all that apply, then submit.
GATE 2025 CS2 · Q35NAT1 mark
Suppose the values 10, −4, 15, 30, 20, 5, 60, 19 are inserted in that order into an initially empty binary search tree. Let T be the resulting binary search tree. The number of edges in the path from the node containing 19 to the root node of T is ______.
GATE 2024 CS2 · Q39MCQ2 marks
You are given a set V of distinct integers. A binary search tree T is created by inserting all elements of V one by one, starting with an empty tree. The tree T follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into T, and you do not have access to T. Which one of the following statements is TRUE?
GATE 2023 · Q47MCQ2 marks
Consider the C function foo and the binary tree shown.
typedef struct node {
int val;
struct node *left, *right;
}
node;
int foo(node *p) {
int retval;
if (p == NULL) return 0;
else {
retval = p->val + foo(p->left) + foo(p->right);
printf("%d ", retval);
return retval;
}
}
The tree: the root 10 has left child 5 and right child 11; node 5 has children 3 (left) and 8 (right); node 11 has only a right child 13. When foo is called with a pointer to the root node of the given binary tree, what will it print?
GATE 2022 · Q28NAT1 mark
Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3rd largest element of the tree is stored at index ______.
GATE 2021 Set 1 · Q10MCQ1 mark
A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?
GATE 2020 · Q5MCQ1 mark
The preorder traversal of a binary search tree is 15, 10, 12, 11, 20, 18, 16, 19. Which one of the following is the postorder traversal of the tree?
GATE 2020 · Q6MCQ1 mark
What is the worst case time complexity of inserting n² elements into an AVL-tree with n elements initially?
GATE 2020 · Q41MCQ2 marks
In a balanced binary search tree with n elements, what is the worst case time complexity of reporting all elements in range [a, b]? Assume that the number of reported elements is k.
GATE 2019 Set 2 · Q46NAT2 marks
Let T be a full binary tree with 8 leaves. (A full binary tree has every level full.) Suppose two leaves a and b of T are chosen uniformly and independently at random. The expected value of the distance between a and b in T (i.e., the number of edges in the unique path between a and b) is (rounded off to 2 decimal places) ______.
GATE 2018 · Q20NAT1 mark
The postorder traversal of a binary tree is 8, 9, 6, 7, 4, 5, 2, 3, 1. The inorder traversal of the same tree is 8, 6, 9, 4, 7, 2, 5, 1, 3. The height of a tree is the length of the longest path from the root to any leaf. The height of the binary tree above is ______.
GATE 2017 Set 1 · Q6MCQ1 mark
Let T be a binary search tree with 15 nodes. The minimum and maximum possible heights of T are: (Note: the height of a tree with a single node is 0.)
GATE 2013 Code A · Q43MCQ2 marks
The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?
GATE 2012 Code A · Q47MCQ2 marks
The height of a tree is defined as the number of edges on the longest path in the tree. The function shown in the pseudocode below is invoked as height(root) to compute the height of a binary tree rooted at the tree pointer root.
int height(treeptr n) {
if (n == NULL) return −1;
if (n→left == NULL) if (n→right == NULL) return 0;
else return [Box 1];
else {
h1 = height(n→left);
if (n→right == NULL) return (1 + h1);
else {
h2 = height(n→right);
return [Box 2];
}
}
}
The appropriate expressions for the two boxes B1 and B2 are
Common traps
Check whether height is counted in edges or nodes; a single node has height 0 in edges, 1 in nodes.
Preorder + postorder is ambiguous for trees with single-child nodes.
A BST requires every node in the left subtree to be smaller, not only the immediate child.
Insertion order changes the shape of a BST; sorted order gives a path.