What are common examiner traps in Binary Search Trees?

Assuming BST search is always O( 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.

Binary Search Trees

21 Qs · since 2011 · 31 marks · 1.2 marks/paperMedium yield

Take topic test

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. Qu… Guide

Type

GATE CSE 2026 Set 1Q40MCQ2 marksMediumLet $P$ be the set of all integers from 1 to 15. Consider any order of insertion of the elements of $P$ into a binary search tree that creates a complete binary tree. Which one of the following elements can NEVER be the third element that is inserted?
GATE CSE 2026 Set 1Q62NAT2 marksEasyThe following sequence corresponds to the preorder traversal of a binary search tree $T$ : $50, 25, 13, 40, 30, 47, 75, 60, 70, 80, 77$ The position of the element 60 in the postorder traversal of $T$ is ________. (answer in integer) Note: The position begins with 1.
GATE CSE 2026 Set 2Q49MSQ2 marksMediumConsider a binary search tree (BST) with $n$ leaf nodes ( $n > 0$ ). Given any node $V$ , the key present in the node is denoted as $Val(V)$ . All the keys present in the given BST are distinct. The keys belong to the set of real numbers. For a node $V$ , let $Suc(V)$ denote the node that is its inorder…
GATE CSE 2025 Set 1Q26MSQ1 markEasyWhich of the following statement(s) is/are TRUE for any binary search tree (BST) having $n$ distinct integers?
GATE CSE 2025 Set 2Q35NAT1 markEasySuppose 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 ________ . (Answer in integer)
GATE CSE 2024 Set 2Q39MCQ2 marksEasyYou 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.…
GATE CSE 2022Q28NAT1 markMediumSuppose 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 $3^{\text{rd}}$ largest element of the tree is stored at index ________.
GATE CSE 2021 Set 1Q10MCQ1 markEasyA 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 CSE 2020Q5MCQ1 markEasyThe 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 CSE 2020Q41MCQ2 marksEasyIn 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 CSE 2017 Set 1Q6MCQ1 markEasyLet $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 CSE 2017 Set 2Q36MCQ2 marksMediumThe pre-order traversal of a binary search tree is given by 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20. Then the post-order traversal of this tree is:
GATE CSE 2016 Set 2Q40NAT2 marksMediumThe number of ways in which the numbers 1, 2, 3, 4, 5, 6, 7 can be inserted in an empty binary search tree, such that the resulting tree has height 6, is _______ . *Note: The height of a tree with a single node is 0.*
GATE CSE 2015 Set 1Q10MCQ1 markEasyWhich of the following is/are correct inorder traversal sequence(s) of binary search tree(s)? I. $3, 5, 7, 8, 15, 19, 25$ II. $5, 8, 9, 12, 10, 15, 25$ III. $2, 7, 10, 8, 14, 16, 20$ IV. $4, 6, 7, 9, 18, 20, 25$
GATE CSE 2015 Set 1Q23MCQ1 markEasyWhat are the worst-case complexities of insertion and deletion of a key in a binary search tree?
GATE CSE 2015 Set 3Q13MCQ1 markEasyWhile inserting the elements 71, 65, 84, 69, 67, 83 in an empty binary search tree (BST) in the sequence shown, the element in the lowest level is
GATE CSE 2014 Set 3Q39NAT2 marksMediumSuppose we have a balanced binary search tree $T$ holding $n$ numbers. We are given two numbers $L$ and $H$ and wish to sum up all the numbers in $T$ that lie between $L$ and $H$ . Suppose there are $m$ such numbers in $T$ . If the tightest upper bound on the time to compute the sum is $O(n^a \log^b n + m^c \log^d n)$ …
GATE CSE 2013Q7MCQ1 markEasyWhich one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of $n$ nodes?
GATE CSE 2013Q43MCQ2 marksMediumThe 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 CSE 2012Q5MCQ1 markEasyThe worst case running time to search for an element in a balanced binary search tree with $n2^n$ elements is
GATE CSE 2011Q29MCQ2 marksEasyWe are given a set of $n$ distinct elements and an unlabeled binary tree with $n$ nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?

Topic guide

What does GATE test in Binary Search Trees?

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( n) height and range query cost O( 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
common · mixed · 2 marks · 2026, 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
common · mixed · 1 marks · 2025, 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
common · mixed · 1.5 marks · 2017, 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
common · MCQ · 1 marks · 2021, 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
occasional · mixed · 2 marks · 2026, 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
occasional · MSQ · 1.5 marks · 2026, 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( 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.

Binary Search Trees

21 Qs · since 2011 · 31 marks · 1.2 marks/paperMedium yield

Take topic test

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. Qu… Guide

Type

Topic guide

What does GATE test in Binary Search Trees?

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( n) height and range query cost O( 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
common · mixed · 2 marks · 2026, 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
common · mixed · 1 marks · 2025, 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
common · mixed · 1.5 marks · 2017, 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
common · MCQ · 1 marks · 2021, 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
occasional · mixed · 2 marks · 2026, 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
occasional · MSQ · 1.5 marks · 2026, 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( 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