GATE CS · DA

Trees, binary search trees and binary heaps

Trees, binary search trees and binary heaps: how hierarchical data is structured, searched and prioritised. These notes cover counting results for binary trees (node bounds, $n_{0} = n_{2} + 1$ , Catalan numbers) and rebuilding a tree from its traversals. They also cover BST search, insert and delete, AVL balance and rotations, and binary heaps: array layout, sift-up and sift-down, $Θ (n)$ build-heap and heap sort. Throughout, the height of a tree is counted in edges: a single node has height 0 and an empty tree has height $- 1$ .

26 previous-year questions · 24 solved · 7 practice questions

Binary trees: structure and counting properties

A binary tree is a rooted tree in which every node has at most two children, distinguished as left and right. Convention used throughout these notes: the height of a tree is the number of edges on the longest root-to-leaf path. A single-node tree has height 0 and an empty tree has height $- 1$ . The depth (or level) of a node is the number of edges from the root to it, so the root is at level 0. Some questions count height or level in nodes instead of edges, with the root at level 1. That shifts every height- and level-based formula below by 1, so always check the convention a question states.

MAXIMUM NODES AT A GIVEN LEVEL

max nodes at level i = 2^{i}

Root at level 0. An upper bound for any binary tree, reached exactly when level $i$ is completely filled.

MAXIMUM NODES IN A TREE OF GIVEN HEIGHT

max nodes for height h = 2^{h + 1} - 1

Reached exactly by a perfect binary tree of height $h$ (every level completely filled).

MINIMUM NODES IN A TREE OF GIVEN HEIGHT

min nodes for height h = h + 1

Reached by any tree with exactly one node per level: left-skewed, right-skewed or zig-zag.

HEIGHT RANGE FOR N NODES

⌊ lo g_{2} n ⌋ \leq h \leq n - 1

The lower bound follows from $n \leq 2^{h + 1} - 1$ . A complete binary tree with $n$ nodes, and so every binary heap, has height exactly $⌊ lo g_{2} n ⌋$ .

LEAVES VERSUS NODES WITH TWO CHILDREN (ANY BINARY TREE)

n_{0} = n_{2} + 1

Holds for every non-empty binary tree, whatever the number $n_{1}$ of one-child nodes. Here $n_{0}$ = leaves and $n_{2}$ = nodes with two children. Proof: count edges two ways. With $n = n_{0} + n_{1} + n_{2}$ nodes there are $n - 1$ edges, and each edge hangs below exactly one parent, so $n - 1 = n_{1} + 2 n_{2}$ . Subtracting gives $n_{0} = n_{2} + 1$ .

FULL (STRICT) BINARY TREE: LEAVES, INTERNAL NODES, TOTAL

L = I + 1, n = 2 I + 1

In a full binary tree every node has 0 or 2 children, so $n_{1} = 0$ . With $I$ internal nodes it has $L = I + 1$ leaves and $n = 2 I + 1$ nodes in all (always odd). More generally, a full $k$ -ary tree (every node has 0 or $k$ children) with $I$ internal nodes has $L = (k - 1) I + 1$ leaves.

Special shapes you must be able to recognise on sight

Full / proper / strict binary tree: every node has exactly 0 or 2 children, never exactly 1.
Complete binary tree: every level is completely filled except possibly the last, and the last level's nodes are as far left as possible, with no gaps. This is exactly the shape a binary heap's array stores.
Perfect binary tree: every internal node has 2 children AND every leaf is at the same level. A perfect tree of height $h$ has $2^{h + 1} - 1$ nodes, of which $2^{h}$ are leaves and $2^{h} - 1$ are internal.
Height-balanced tree: at every node, the heights of the left and right subtrees differ by at most a fixed bound (for AVL trees, at most 1). Balance limits the worst-case height, not the node count.

EXAM TIP

Terminology varies. Some texts use 'complete binary tree' for what these notes call perfect, and 'almost complete' for what these notes call complete. Use the definition the question gives. A complete tree need not have all leaves on one level; only the last level must be filled from the left. Sanity check: a tree with $n$ nodes always has exactly $n - 1$ edges.

Tree traversals and reconstruction

The four standard traversals

Preorder: visit the root, then traverse the left subtree, then the right subtree (root, left, right).
Inorder: traverse the left subtree, visit the root, then traverse the right subtree (left, root, right). On a BST this visits the keys in increasing order.
Postorder: traverse the left subtree, then the right subtree, then visit the root (left, right, root).
Level-order (BFS): visit nodes level by level, left to right within a level. It is implemented with a queue: enqueue the root, then repeatedly dequeue a node, visit it and enqueue its non-null children.

Rebuilding a unique tree from traversals (all keys distinct):

Inorder + preorder or inorder + postorder determines the binary tree uniquely. Take the root from the preorder (first element) or the postorder (last element), find it in the inorder sequence to split the left and right subtrees, and recurse.
Inorder + level-order also determines it uniquely.
Preorder + postorder does NOT determine a general binary tree. If a node has a single child, that child can be its left or its right child without changing either sequence. If the tree is known to be full (every node has 0 or 2 children), preorder + postorder do determine it.
For a BST, one traversal is enough, because its inorder sequence is just the keys sorted. Equivalently, inserting the keys into an empty BST in preorder order, in level order, or in reverse postorder order rebuilds the same tree. Each of these orders lists every parent before its children.

WORKED EXAMPLE

A binary tree has inorder traversal D B E A F C G and preorder traversal A B D E C F G. Rebuild the tree and give its postorder traversal.

Solution

Root = first element of the preorder = A.
Split the inorder at A: left = D B E, right = F C G (3 nodes each).
Split the rest of the preorder, B D E C F G, by those sizes: left preorder = B D E, right preorder = C F G.
Left subtree (inorder D B E, preorder B D E): the root is B. The inorder splits into D | B | E, so B's left child is D and its right child is E.
Right subtree (inorder F C G, preorder C F G): the root is C. The inorder splits into F | C | G, so C's left child is F and its right child is G.
The tree is A(left = B(left = D, right = E), right = C(left = F, right = G)).
Postorder (left, right, root): B's subtree gives D, E, B; C's subtree gives F, G, C; then the root A.

Answer: Postorder = D E B F G C A

These traversal functions assume a node with data, left and right fields. Code-tracing questions are built on this pattern.

#include <stdio.h>

struct Node {
    int data;
    struct Node *left, *right;
};

void preorder(struct Node *root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

void inorder(struct Node *root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

void postorder(struct Node *root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

Trace of the preorder function on the tree from the worked example (letters stand for the stored values):

preorder(A) prints A, then calls preorder(B).
preorder(B) prints B, then calls preorder(D). D is a leaf: it prints D, and both of its recursive calls get NULL and return at once.
Back in B, preorder(E) prints E. B's call then returns to A.
A calls preorder(C), which prints C, then F (leaf), then G (leaf).

Output: A B D E C F G, the given preorder, which confirms the rebuilt tree. The same tree gives inorder D B E A F C G and postorder D E B F G C A.

Binary search trees (BST)

A binary search tree on distinct keys satisfies, at every node: every key in the left subtree is smaller than the node's key, and every key in the right subtree is larger. Search, insert and delete therefore each follow one comparison-guided path down from the root, so each costs $O (h)$ time, where $h$ is the current height. The tree's shape, and so $h$ , depends on the order in which the keys were inserted.

BST operations

Search(key): start at the root. If the key equals the current node's key, it is found. If it is smaller, go left; if larger, go right. Reaching NULL means the key is absent.
Insert(key): search for the key as above until you reach NULL, then attach a new leaf holding the key at that spot.
Delete(key) has three cases. (1) The node is a leaf: remove it. (2) The node has exactly one child: link that child directly to the node's parent in its place. (3) The node has two children: copy into it the key of its inorder successor, the minimum of its right subtree (go right once, then left as far as possible). Then delete the successor from its old position. The successor has no left child, so that deletion is case 1 or case 2. Alternatively use the inorder predecessor, the maximum of the left subtree. The two choices give different trees, and a question will say which one it uses.

BST HEIGHT FOR N KEYS

⌊ lo g_{2} n ⌋ \leq h \leq n - 1

The lower bound holds when the tree is complete. The upper bound is a chain, and every operation then costs $Θ (n)$ in the worst case. Sorted or reverse-sorted input gives a chain, but so do other orders, such as 1, 5, 2, 4, 3. Of the $n!$ insertion orders of $n$ distinct keys, exactly $2^{n - 1}$ give height $n - 1$ . When all insertion orders are equally likely, the expected height is $Θ (lo g n)$ .

Recursive BST insert in C:

#include <stdlib.h>

struct Node* insert(struct Node *root, int key) {
    if (root == NULL) {
        struct Node *n = malloc(sizeof(struct Node));
        n->data = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key < root->data)
        root->left = insert(root->left, key);
    else if (key > root->data)
        root->right = insert(root->right, key);
    /* key == root->data: a duplicate, ignored (keys assumed distinct) */
    return root;
}

Trace: inserting 40, 20, 60, 10, 30 in that order makes 40 the root, with 20 on its left and 60 on its right. Then 10 becomes the left child of 20 and 30 its right child. The height is 2: this order does not produce a chain.

WORKED EXAMPLE

Keys 50, 30, 70, 20, 40, 60, 80 are inserted in that order into an empty BST. Then 50 is deleted, replacing it with its inorder successor. What does the tree look like afterwards?

Solution

After the insertions: root 50 has left child 30 (children 20 and 40) and right child 70 (children 60 and 80), a perfect tree of height 2.
50 has two children, so this is case 3. Its inorder successor is the minimum of the right subtree: go right to 70, then left to 60. 60 has no left child, so 60 is the successor.
Copy 60 into the root, then delete the old 60. It is a leaf (case 1), so 70 loses its left child.
Check: the inorder is 20 30 40 60 70 80, which is sorted, so the tree is still a BST.

Answer: Root 60; left subtree 30 (20, 40); right subtree 70 with only a right child, 80. Using the inorder predecessor instead would give root 40, with 30 keeping only its left child 20.

EXAM TIP

BST search, insert and delete are all $O (h)$ . They are $O (lo g n)$ in the worst case only for balanced search trees such as AVL or red-black trees, which keep $h = O (lo g n)$ . Never assume a plain BST is balanced unless the question says so.

AVL trees: self-balancing BSTs

An AVL tree is a BST that restores one extra rule after every insertion and deletion: at every node, the heights of the left and right subtrees differ by at most 1. This keeps the height $O (lo g n)$ , so search, insert and delete each take $O (lo g n)$ time in the worst case.

BALANCE FACTOR

BF(node) = height(left subtree) - height(right subtree)

An AVL tree needs $BF \in {- 1, 0, 1}$ at every node, with the height of an empty subtree taken as $- 1$ . A node whose BF becomes $+ 2$ or $- 2$ after an update must be rebalanced by rotation.

MINIMUM NODES IN AN AVL TREE OF HEIGHT H

N (h) = N (h - 1) + N (h - 2) + 1, N (0) = 1, N (- 1) = 0

The sparsest AVL tree of height $h$ is a root whose two subtrees are sparsest AVL trees of heights $h - 1$ and $h - 2$ . This gives $N (0), N (1), \dots = 1, 2, 4, 7, 12, 20, 33, \dots$ and in closed form $N (h) = F_{h + 3} - 1$ , where $F_{1} = F_{2} = 1$ are the Fibonacci numbers. Consequently an AVL tree with $n$ nodes has height $h < 1.4405 lo g_{2} (n + 2) - 0.3277$ , which is $O (lo g n)$ . The maximum number of nodes of height $h$ is $2^{h + 1} - 1$ , as for any binary tree.

Rotation cases after an insertion (z = the lowest unbalanced ancestor of the new node)

Case	Where the new node went	Fix
Left-Left (LL)	Left subtree of z's left child	Single right rotation at z
Right-Right (RR)	Right subtree of z's right child	Single left rotation at z
Left-Right (LR)	Right subtree of z's left child	Left rotation at z's left child, then right rotation at z
Right-Left (RL)	Left subtree of z's right child	Right rotation at z's right child, then left rotation at z

WORKED EXAMPLE

Insert 30, 10, 20 in that order into an empty AVL tree. Show the rebalancing.

Solution

Insert 30: the root. Insert 10: the left child of 30. Insert 20: it is smaller than 30 and larger than 10, so it becomes the right child of 10.
Heights: 20 has height 0; 10 has height 1 (left empty, height $- 1$ ), so BF(10) = $- 1 - 0 = - 1$ ; 30 has height 2, with BF(30) = $1 - (- 1) = 2$ . The lowest unbalanced node is z = 30.
The new node is in the right subtree of z's left child: the LR case.
Left rotation at 10: 20 takes 10's place as the left child of 30, with 10 as 20's left child.
Right rotation at 30: 20 becomes the root, with left child 10 and right child 30. All balance factors are now 0.

Answer: Root 20, left child 10, right child 30 (height 1)

EXAM TIP

After one insertion, rebalancing the lowest unbalanced ancestor with a single or double rotation restores the height that subtree had before the insertion, so every ancestor above it is balanced again. At most one rotation (single or double) is needed per insertion. Deletion is different: a rotation can reduce a subtree's height and unbalance an ancestor further up, so one deletion may need a rotation at each level up to the root, which is $O (lo g n)$ rotations.

Binary heaps

A binary heap is a complete binary tree stored in an array with no pointers, which obeys the heap-order property. In a max-heap every parent's key is $\geq$ each of its children's keys, so the maximum is at the root. A min-heap reverses the inequality. Heap order says nothing about left versus right: unlike in a BST, siblings and cousins can be in any relative order.

Array representation

0-indexed: the node at index $i$ has its left child at $2 i + 1$ , its right child at $2 i + 2$ (when within bounds) and its parent at $⌊(i - 1) /2 ⌋$ for $i > 0$ .
1-indexed: the node at index $i$ has its children at $2 i$ and $2 i + 1$ and its parent at $⌊ i /2 ⌋$ . Check which convention a question uses before computing any index.
Any array, read level by level, is a complete binary tree. Whether it is a heap depends only on the heap-order checks between each parent and its children.

HEIGHT, LEAVES AND INTERNAL NODES OF AN N-ELEMENT HEAP

h = ⌊ lo g_{2} n ⌋, leaves = ⌈ \frac{n}{2} ⌉, internal = ⌊ \frac{n}{2} ⌋

In the 1-indexed layout the leaves are at indices $⌊ n /2 ⌋ + 1$ to $n$ ; in the 0-indexed layout at $⌊ n /2 ⌋$ to $n - 1$ . In a max-heap with distinct keys the minimum is always at a leaf, since an internal node has a smaller child, and it can be at any leaf. Finding it therefore means scanning the $⌈ n /2 ⌉$ leaves, which is $Θ (n)$ .

BUILD-HEAP RUNNING TIME

Θ (n)

Bottom-up build-heap calls sift-down (heapify) on every internal node, from the last one back to the root. An $n$ -element heap has at most $⌈ n / 2^{h + 1} ⌉$ nodes at height $h$ , and sifting one down costs $O (h)$ . The total is $O (n \sum_{h \geq 0} h / 2^{h}) = O (n)$ , because $\sum_{h \geq 0} h / 2^{h} = 2$ . It is linear, NOT $Θ (n lo g n)$ . Building by $n$ successive inserts instead costs $O (n lo g n)$ in the worst case.

HEAP SORT

Θ (n lo g n) time (worst case), O (1) auxiliary space

Build a max-heap in $Θ (n)$ . Then $n - 1$ times: swap the root with the last element of the heap, shrink the heap by 1 and sift down the new root, each costing $O (lo g n)$ . It sorts in place and is not stable. $O (1)$ auxiliary space assumes an iterative sift-down; the recursive maxHeapify below uses $O (lo g n)$ stack space.

Cost of binary max-heap operations (n elements, worst case)

Operation	Cost
Find max	$O (1)$
Insert	$O (lo g n)$
Extract max (delete root)	$O (lo g n)$
Increase key / delete the element at a known index	$O (lo g n)$
Search for an arbitrary key; find min	$O (n)$
Build-heap (bottom-up)	$Θ (n)$
$n$ successive inserts into an empty heap	$O (n lo g n)$
Merge two heaps of sizes $n$ and $m$ (concatenate, then build-heap)	$O (n + m)$

Insert and delete-max procedures (max-heap)

Insert(key): put the key in the next free array slot, the end of the complete tree. Then sift up: while it is not the root and is greater than its parent, swap it with its parent. Worst case $O (lo g n)$ .
Delete-max (extract-max): save the root's value as the answer. Move the LAST element of the array into the root and shrink the heap by 1. Then sift down the new root: while it has a child larger than itself, swap it with the larger of its children. Worst case $O (lo g n)$ .

Sift-down (max-heapify) and build-heap in C, 0-indexed:

void maxHeapify(int a[], int n, int i) {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
    if (l < n && a[l] > a[largest]) largest = l;
    if (r < n && a[r] > a[largest]) largest = r;
    if (largest != i) {
        int t = a[i];
        a[i] = a[largest];
        a[largest] = t;
        maxHeapify(a, n, largest);
    }
}

void buildMaxHeap(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        maxHeapify(a, n, i);
}

WORKED EXAMPLE

Build a max-heap (0-indexed) from the array [4, 10, 3, 5, 1, 15] with bottom-up build-heap.

Solution

$n = 6$ , so the last internal node is at index $6/2 - 1 = 2$ . maxHeapify runs for $i = 2, 1, 0$ in that order; the leaves at indices 3, 4, 5 need no work.
$i = 2$ (value 3): the left child is at index 5 (value 15); the right child, index 6, is out of range. 15 > 3, so swap: [4, 10, 15, 5, 1, 3]. Index 5 is a leaf, so stop.
$i = 1$ (value 10): the children are at index 3 (value 5) and index 4 (value 1). 10 is the largest of the three: no swap.
$i = 0$ (value 4): the children are at index 1 (value 10) and index 2 (value 15). The largest is 15, so swap: [15, 10, 4, 5, 1, 3]. Continue at index 2 (value 4): its only child is at index 5 (value 3), and 4 > 3, so stop.

Answer: Max-heap array: [15, 10, 4, 5, 1, 3]

WORKED EXAMPLE

Perform one extract-max on the max-heap [15, 10, 4, 5, 1, 3] (0-indexed).

Solution

Save the root, 15, as the answer. Move the last element, 3, to the root and shrink the heap to 5 elements: [3, 10, 4, 5, 1].
Sift down from index 0 (value 3): the children are 10 (index 1) and 4 (index 2). The larger is 10, and 10 > 3, so swap: [10, 3, 4, 5, 1].
Continue at index 1 (value 3): the children are 5 (index 3) and 1 (index 4). The larger is 5, and 5 > 3, so swap: [10, 5, 4, 3, 1].
Index 3 is a leaf, so stop. Check: 10 ≥ 5, 4; 5 ≥ 3, 1.

Answer: Returns 15; the heap becomes [10, 5, 4, 3, 1]

EXAM TIP

Build-heap must process nodes bottom-up, from the last internal node back to the root. A single top-down pass, running sift-down from index 0 forwards, does NOT produce a heap in general. Building by $n$ successive inserts does give a valid heap, but it may be a different array from the one bottom-up build-heap gives, so follow the method the question names.

Counting binary trees and BSTs: Catalan numbers

The number of different binary tree shapes with $n$ nodes equals the number of different BSTs on $n$ distinct keys. Once the shape is fixed, the BST property forces the sorted keys into its positions in inorder order, so each shape carries exactly one BST. Both counts are the $n$ -th Catalan number.

CATALAN NUMBER

C_{n} = \frac{1}{n + 1} (n 2 n) = \frac{( 2 n )!}{( n + 1 )! n !}, C_{0} = 1, C_{n} = i = 0 \sum n - 1 C_{i} C_{n - 1 - i}

The recurrence chooses the root's left subtree size $i$ ; the right subtree then has $n - 1 - i$ nodes. The first values are $C_{0}, \dots, C_{6} = 1, 1, 2, 5, 14, 42, 132$ . $C_{n}$ is the number of binary tree shapes with $n$ nodes and the number of BSTs on $n$ distinct keys. It also counts the ways to fully parenthesise a product of $n + 1$ factors, and the balanced bracket strings of length $2 n$ . If $n$ distinct labels may be placed freely in the nodes (no BST rule), the number of labelled binary trees is $n! C_{n}$ .

WORKED EXAMPLE

How many different binary tree shapes have exactly 3 nodes?

Solution

$C_{3} = \frac{1}{4} (3 6) = \frac{1}{4} \times 20 = 5$ .
Check by listing them. One shape has a root with two leaf children. In the other four the root has a single 2-node subtree: that subtree can be on the left or the right, and it has 2 shapes of its own. These four are the two straight chains (left-left, right-right) and the two zig-zags (left-right, right-left). That makes $1 + 4 = 5$ . So 3 distinct keys give exactly 5 BSTs.

Answer: 5

PREVIOUS-YEAR QUESTIONS

26 questions from the CS and DA papers

Try each question first, then open the answer. 2 show the official answer only. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 1 · GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2022 · GATE CSE 2020 · GATE CSE 2018 · GATE DA 2026 · GATE DA 2024

GATE 2026 CS1 Q.23

GATE 2026 · CS1Q.23 · 1 mark · MSQ

Let $n$ be an odd number greater than 100. Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from 1.

Which of the following indices of $P$ do/does NOT correspond to any leaf node of the minheap?

(A)
$\frac{n + 1}{2}$
(B)
$\frac{n - 1}{2}$
(C)
$\frac{n - 3}{2}$
(D)
$n$

Answer and solution

GATE 2026 CS1 Q.23: answer and solution

See the question in the paper

Trees, binary search trees and binary heaps

Binary trees: structure and counting properties

Tree traversals and reconstruction

Binary search trees (BST)

AVL trees: self-balancing BSTs

Binary heaps

Counting binary trees and BSTs: Catalan numbers

26 questions from the CS and DA papers

7 questions to test yourself