Trees & BST
Binary trees, traversals, BST operations, AVL rotations — the highest-scoring Data Structures topic in GATE CS. Expect 2–4 marks every year.
Last updated: April 2026 | GATE CS 2024–2026 syllabus
Key Takeaways
- Binary tree: each node has at most 2 children. Height h → min nodes = h+1, max nodes = 2h+1−1.
- Traversals: Inorder (LNR) = sorted output for BST. Preorder (NLR) = serialise/copy. Postorder (LRN) = delete/expression eval. Level-order = BFS.
- BST: left subtree < node < right subtree. Search/insert/delete O(h); h = O(log n) balanced, O(n) skewed.
- BST delete: replace with inorder successor (smallest in right subtree) or inorder predecessor.
- AVL tree: height-balanced BST. Balance factor (BF) = height(left) − height(right) ∈ {−1, 0, +1}.
- AVL rotations: LL (single right), RR (single left), LR (double: left then right), RL (double: right then left).
- AVL height: for n nodes, h = O(log n). Min nodes in AVL of height h: N(h) = N(h-1) + N(h-2) + 1 (Fibonacci-like).
1. Tree Terminology & Properties
| Term | Definition |
|---|---|
| Root | Top node; no parent |
| Leaf | Node with no children |
| Height of node | Longest path from node to a leaf. Leaf height = 0. |
| Height of tree | Height of root. Empty tree height = −1 (or 0 by some definitions). |
| Depth of node | Distance from root to node. Root depth = 0. |
| Level | depth + 1 (root at level 1) — or same as depth (root at level 0). GATE uses depth = 0 for root. |
| Full binary tree | Every node has 0 or 2 children. |
| Complete binary tree | All levels filled except possibly last; last level filled left to right. |
| Perfect binary tree | All leaves at same level. Nodes = 2h+1−1. |
Complete binary tree with n nodes: Height = ⌊log2n⌋
Nodes at level d: at most 2d
2. Binary Tree Traversals
| Traversal | Order | Time | Key Use |
|---|---|---|---|
| Inorder | Left → Root → Right | O(n) | Sorted output of BST |
| Preorder | Root → Left → Right | O(n) | Tree serialisation, copy |
| Postorder | Left → Right → Root | O(n) | Tree deletion, expression evaluation |
| Level-order | Level by level (BFS) | O(n) | BFS, height calculation |
3. Binary Search Tree (BST)
For every node N: all keys in left subtree < N.key < all keys in right subtree.
This is the most-tested BST property in GATE.
| Operation | Average | Worst (skewed) |
|---|---|---|
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
| Delete | O(log n) | O(n) |
| Min/Max | O(log n) | O(n) |
| Inorder traversal | O(n) | O(n) |
4. BST Operations
Search
Compare key with node. If equal, found. If key < node.key, go left. If key > node.key, go right. O(h).
Insert
Search for key (will fail for a new key). Insert as leaf at the position where search failed. O(h).
Delete — Three Cases
Case 2 — One child: Replace node with its child.
Case 3 — Two children: Replace node’s key with its inorder successor (minimum of right subtree) or inorder predecessor (maximum of left subtree). Delete the successor/predecessor (which has at most one child → reduces to Case 1 or 2).
5. AVL Trees
An AVL tree is a height-balanced BST where for every node, |height(left) − height(right)| ≤ 1.
Valid BF values: −1, 0, +1
BF = +2 → left-heavy (need right rotation or LR). BF = −2 → right-heavy (need left rotation or RL).
Height of AVL with n nodes: h = O(log n) — specifically h ≤ 1.44 log2(n+2)
Minimum nodes N(h) at height h: N(0)=1, N(1)=2, N(h)=N(h-1)+N(h-2)+1
| Height | Min Nodes |
|---|---|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |
| 3 | 7 |
| 4 | 12 |
| h | N(h-1)+N(h-2)+1 |
6. AVL Rotations
| Imbalance Type | BF of Z | BF of child | Rotation |
|---|---|---|---|
| LL (Left-Left) | +2 | +1 or 0 | Single right rotation at Z |
| RR (Right-Right) | −2 | −1 or 0 | Single left rotation at Z |
| LR (Left-Right) | +2 | −1 | Left rotate left child, then right rotate Z |
| RL (Right-Left) | −2 | +1 | Right rotate right child, then left rotate Z |
Y = Z.left; Z.left = Y.right; Y.right = Z; update heights.
Y becomes the new root of this subtree.
Left rotation at Z (RR case):
Y = Z.right; Z.right = Y.left; Y.left = Z; update heights.
After each insertion, update balance factors on the path from inserted node to root. Rebalance at the first unbalanced ancestor. At most 1 rotation (single or double) is needed after insertion. After deletion, up to O(log n) rotations may be needed.
7. Key Formulae
| Property | Formula |
|---|---|
| Max nodes at height h | 2h+1 − 1 |
| Min nodes at height h (binary tree) | h + 1 |
| Height of complete BT with n nodes | ⌊log2n⌋ |
| Leaves in full binary tree with n nodes | (n+1)/2 |
| n0 = n2 + 1 (full BT) | Leaves = 2-child nodes + 1 |
| Min nodes in AVL of height h | N(h) = N(h-1)+N(h-2)+1 |
| Max height of AVL with n nodes | 1.44 log2(n+2) |
| BST nodes with keys 1 to n | Catalan number C(n) = C(2n,n)/(n+1) |
8. GATE CS Solved Examples
Example 1 — n0 = n2 + 1 (GATE CS 2019)
Q: A full binary tree has 21 internal nodes (with 2 children). How many leaves?
Example 2 — AVL insertion (GATE CS 2020)
Q: Insert 10, 20, 30 into an empty AVL tree. Show the tree after each insertion.
Solution:
- Insert 10: [10] — balanced.
- Insert 20: [10, right=20] — BF(10) = −1, balanced.
- Insert 30: BF(10) = −2, right child 20 has BF = −1 → RR case → left rotate at 10.
Example 3 — BST from preorder (GATE CS 2022)
Q: Preorder traversal of BST: 30, 20, 10, 25, 40, 35, 50. What is the inorder traversal?
Solution: Reconstruct BST by inserting in preorder sequence. Inorder = sorted = 10, 20, 25, 30, 35, 40, 50.
9. Common Mistakes
Mistake 1 — Height vs depth confusion
Height is measured from a node downward to the farthest leaf. Depth is from root to the node. Root has height = h (tree height), depth = 0. Leaf has height = 0.
Mistake 2 — BST delete: wrong successor
Inorder successor = minimum of right subtree (not the right child). Inorder predecessor = maximum of left subtree (not left child). These could be several levels down.
Mistake 3 — AVL rotation type identification
Identify LL/RR/LR/RL by where the new node was inserted relative to the unbalanced ancestor. LR: inserted in right subtree of left child. RL: inserted in left subtree of right child.
Mistake 4 — Preorder+postorder unique tree
Preorder + postorder does NOT uniquely determine the tree when a node has a single child (it could be a left or right child). Only inorder + preorder (or inorder + postorder) guarantees uniqueness.
Mistake 5 — AVL min nodes formula
Min nodes at height h: N(h) = N(h-1) + N(h-2) + 1 with N(0)=1, N(1)=2. Forgetting the +1 (for the root) is the most common error.
10. FAQ
What is the minimum and maximum number of nodes in a binary tree of height h?
Minimum: h+1 (skewed chain). Maximum: 2h+1−1 (perfect binary tree).
What are the four types of AVL rotations?
LL (single right), RR (single left), LR (left rotate child + right rotate parent), RL (right rotate child + left rotate parent). Identify the case by looking at BF of the unbalanced node and its heavier child.
What is the time complexity of BST operations in the worst case?
O(n) for a skewed tree (sorted insertion). O(log n) average and for balanced BSTs. AVL guarantees O(log n) worst case.
What is the difference between inorder, preorder, and postorder traversal?
Inorder (LNR): sorted BST output. Preorder (NLR): tree copy/serialise. Postorder (LRN): deletion/expression eval. Level-order: BFS using queue.