What are common examiner traps in Binary Search Trees?

Assuming BST search is always O(log n) and forgetting worst-case unbalanced/skewed tree is O(n). Off-by-one errors in height definitions: GATE standardizes single-node tree height as 0 (unless stated otherwise), making root-to-leaf path length equal to height. Confusing 0-indexed vs. 1-indexed complete tree array layouts (2i+1 vs. 2i). Assuming an element can be inserted at any time in a fixed shape tree, forgetting that all its ancestor keys must be inserted before it. Assuming min-heap and BST properties can coexist for arbitrary binary trees; BST left children are strictly smaller than parents, violating min-heap property. Counting nodes instead of edges (or vice-versa) when determining path lengths from a node to the root.

GATE CSE Binary Search Trees PYQs

Medium yield12.6% of Programming and Data Structures

Binary Search Trees (BSTs) in GATE CS test a balance of traversal mechanics, structural properties, worst-case vs. balanced-case complexities, and sequential in… Read the guide

Take topic test

Questions: 21
Asked: since 2011
Total marks: 31
Marks / paper: 1.2

21 GATE CSE Binary Search Trees PYQs with solutions, from Programming and Data Structures. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Binary Search Trees

Concepts, patterns, formulas and traps distilled from past papers.

Binary Search Trees (BSTs) in GATE CS test a balance of traversal mechanics, structural properties, worst-case vs. balanced-case complexities, and sequential insertion dynamics. Questions frequently test the fundamental invariant that an inorder traversal yields a strictly sorted sequence, enabling unique reconstruction from preorder or postorder alone. Recent years (2022–2026) show a noticeable shift toward structural constraints (complete BSTs, heap/array indexing, ancestor insertion order dependencies, and successor relationships).

Core concepts

Strict sortedness of inorder traversal for distinct keys
Uniqueness of BST reconstruction given preorder or postorder traversal
Degenerate / skewed BST structure and worst-case O(n) search/insert/delete complexity
Balanced BST O(log n) height and range query cost O(log n + m)
Ancestor insertion dependency in BST construction
Array representation indexing for complete BSTs
Inorder successor and predecessor properties (especially at leaf nodes)
Constant-time heuristics (e.g., picking any key smaller than the maximum via root / left child)

Recurring question patterns

Preorder to Postorder Conversion / Traversal Indexing
Commonmixed2 marks2026, 2020, 2017, 2013
Given the preorder traversal sequence of a BST, deduce its unique structure (since inorder is implicit by sorting the keys) and find either the complete postorder traversal sequence or the 1-based position of a specific element.
Sequential Insertion & Resulting Tree Structure
Commonmixed1 marks2025, 2015
Simulate the sequential insertion of a given list of keys into an initially empty BST to determine node depths, lowest level elements, ancestor-descendant relationships, or edge distances to the root.
BST Structural Combinatorics and Height Extremes
Commonmixed1.5 marks2017, 2016, 2011
Determine the minimum/maximum height of a BST with $n$ nodes, the number of insertion permutations yielding a degenerate chain ( $2^{n-1}$ ), or the number of ways to populate an unlabeled binary tree structure ( $1$ way).
Time Complexity of BST Operations & Range Queries
CommonMCQ1 marks2021, 2015, 2014, 2013
Evaluate worst-case vs. balanced-case time complexities for search, insert, delete ( $O(n)$ vs. $O(\log n)$ ), non-trivial queries like finding an element smaller than the maximum ( $O(1)$ ), or range-search reporting ( $O(\log n + m)$ ).
Complete/Perfect BST Array Indexing & Insertion Constraints
Occasionalmixed2 marks2026, 2022
Exploit complete binary tree array mappings ( $2i+1, 2i+2$ ) or ancestor-descendant dependencies to identify element positions (e.g., $k^{\text{th}}$ largest element) or deduce invalid insertion prefixes.
Theoretical / Property-Based True-False & MSQ
OccasionalMSQ1.5 marks2026, 2025, 2024
Multi-statement verification involving fundamental properties: inorder uniquely determined from set $V$ , heap vs. BST comparison, max path lengths, and insertion between leaves and inorder successors.

Formulas GATE uses

Permutations for Degenerate (Skewed) BST of Height $n-1$

2^{n-1}

Used to count valid insertion sequences of $n$ distinct elements that result in a completely skewed BST (linear chain of height $n-1$ , where height of single node is 0).

Minimum and Maximum Heights for $n$ Nodes

h_{\min} = \lfloor \log_2 n \rfloor, \quad h_{\max} = n - 1

Used when computing height bounds of arbitrary BSTs with $n$ nodes (under single-node height = 0 convention).

Complete Binary Tree 0-Indexed Array Mapping

\text{left}(i) = 2i + 1, \quad \text{right}(i) = 2i + 2, \quad \text{parent}(i) = \lfloor (i - 1)/2 \rfloor

Used when navigating complete BSTs stored contiguously in an array to locate root, extreme keys, or children.

Range Search Time Complexity in Balanced BST

T(n, m) = O(\log n + m)

Used for finding and summing/reporting all $m$ keys falling within an interval $[L, H]$ in a balanced BST of size $n$ .

Substitutions in Balanced BST Height

T(N) = \Theta(\log N) = \Theta(\log(n \cdot 2^n)) = \Theta(n + \log n) = \Theta(n)

Used when analyzing search complexities where the number of elements $N$ is expressed as an asymptotic function of another parameter $n$ .

Examiner traps in Binary Search Trees

Assuming BST search is always O(log n) and forgetting worst-case unbalanced/skewed tree is O(n).
Off-by-one errors in height definitions: GATE standardizes single-node tree height as 0 (unless stated otherwise), making root-to-leaf path length equal to height.
Confusing 0-indexed vs. 1-indexed complete tree array layouts (2i+1 vs. 2i).
Assuming an element can be inserted at any time in a fixed shape tree, forgetting that all its ancestor keys must be inserted before it.
Assuming min-heap and BST properties can coexist for arbitrary binary trees; BST left children are strictly smaller than parents, violating min-heap property.
Counting nodes instead of edges (or vice-versa) when determining path lengths from a node to the root.

How questions are asked

Preorder/postorder array sequence conversion
Finding the 1-based traversal rank/index of a specific key (NAT)
Simulating sequential insertions and reporting edge/depth distance
Counting insertion permutations that satisfy a structural constraint (e.g., maximum height)
Locating kth largest/smallest elements in complete BST array representation
Multi-statement conceptual validation (MSQ) on BST invariants and successor properties

Paper trends

Shift from standard preorder-to-postorder MCQ conversions to NAT questions asking for the exact numeric index/position of a node in a specific traversal.
2026, 2020, 2017, 2013
Introduction of conceptual MSQs testing deep structural invariants (e.g., inorder successors of leaf nodes, heap comparison, path length bounds).
2026, 2025
Integration of BST properties with complete binary tree / heap array layout mathematics.
2026, 2022

Difficulty notes

Easy questions (1 mark) test direct BST insertion tracing, identifying valid sorted inorder sequences, simple time complexities, or standard min/max height formulas. Medium questions (2 marks) test tree reconstruction with follow-up index queries, combinatorial counts of insertion sequences, multi-parameter range search bounds, or ancestor-dependency constraints on complete BSTs.