Free lesson · DSA Mastery - Interview Prep, End to End

Introduction to BST and Ordered Sets

Medium6 min readdsabst-ordered-set

Introduction to BST and Ordered Sets

The previous section treated the binary tree as a general shape and used the binary-search-tree property opportunistically - inorder traversal happens to visit a BST's values in sorted order. This section flips the relationship: the BST is now a first-class data structure whose entire reason for existing is to keep a set of values ordered under change. Search, insert, delete, find-the-next-larger, find-everything-in-a-range - a BST does all of these in time proportional to its height, which is why it underlies the ordered-map and ordered-set types in essentially every standard library.

This is the introduction to the section. It defines the BST invariant precisely, explains why that invariant makes search logarithmic (when the tree is balanced), introduces the ordered-set abstraction that BSTs implement, and sets up the recurring tension of the section - balance - that determines whether operations are fast or degenerate to a linked list.

The BST Invariant

A binary search tree is a binary tree with one rule, applied at every node:

For every node, all values in its left subtree are less than the node's value, and all values in its right subtree are greater.

That's it. The rule is recursive - it holds at the root, and it holds independently within every subtree. The consequence is profound: at any node, the node's value partitions the remaining values into "smaller, go left" and "larger, go right." This is the same decision a binary search makes on a sorted array, which is exactly where the name comes from.

Important: The BST invariant is global, not local. It is not enough that each node's immediate left child is smaller and right child is larger. Every descendant in the left subtree must be smaller than the node, including descendants several levels down. This is the trap that the Validate Binary Search Tree problem in the previous section was built around, and it remains the single most important thing to internalize about BSTs.

Most BSTs in interview problems hold distinct values (no duplicates). When duplicates are allowed, a convention must be fixed - typically "equal values go right" (or left) consistently - and stated explicitly. Unless a problem says otherwise, assume distinct values.

Why Search Is Logarithmic

To find a value, start at the root and compare. If the target equals the node, done. If it's smaller, the invariant guarantees it can only be in the left subtree, so discard the entire right subtree and recurse left. If larger, discard the left and go right. Each comparison eliminates one subtree - roughly half the remaining nodes when the tree is balanced.

graph TD
    A["compare target to node"] --> B{"target == node.val?"}
    B -->|Yes| C["found"]
    B -->|target < node.val| D["go left (right subtree discarded)"]
    B -->|target > node.val| E["go right (left subtree discarded)"]
    D --> A
    E --> A

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows BST search. At each node we compare the target to the node's value; equal means found, smaller means go left discarding the right subtree, larger means go right discarding the left subtree.

The work is proportional to the length of the path from the root to where the search stops - the tree's height, h. In a balanced tree, h is about log n, so search, insert, and delete are all O(log n). The catch is in that word "balanced."

The Balance Problem

Nothing in the BST invariant forces the tree to be short. Insert the values 1, 2, 3, 4, 5 in order, always going right, and you get a degenerate tree - a straight chain, indistinguishable in shape from a linked list, with height n − 1. Every operation on it is O(n), and the logarithmic promise evaporates.

graph TD
    subgraph Balanced["Balanced: height ~ log n"]
        B3((3)) --> B1((1))
        B3 --> B5((5))
        B1 --> B0((0))
        B1 --> B2((2))
        B5 --> B4((4))
        B5 --> B6((6))
    end
    subgraph Degenerate["Degenerate: height n-1"]
        D1((1)) --> D2((2))
        D2 --> D3((3))
        D3 --> D4((4))
        D4 --> D5((5))
    end

    style B3 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B1 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B5 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B0 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B2 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B4 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style B6 fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D1 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style D2 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style D3 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style D4 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style D5 fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This diagram contrasts two BSTs holding similar values. The balanced tree has height about log n with the root in the middle. The degenerate tree, built by inserting sorted values in order, is a straight right-leaning chain with height n minus one, behaving like a linked list.

This is the central tension of the section. The plain BST operations you'll learn - search, insert, delete - are all O(h), which is wonderful if h is logarithmic and disastrous if it isn't. Self-balancing variants (AVL trees, red-black trees) perform rotations during insertion and deletion to keep h at O(log n) regardless of insertion order. We won't implement a full self-balancing tree in this section, but understanding why balance matters frames every operation here, and the Balance a BST problem from the previous section already showed the brute-force fix: rebuild from the sorted values.

Note: In production, you rarely hand-roll a BST. You reach for the language's ordered-set or ordered-map, which is a balanced BST (commonly a red-black tree) under the hood. The point of learning the raw operations is to understand what that library type does, to handle interview problems that hand you a raw TreeNode BST, and to recognize when an ordered structure is the right tool.

The Ordered Set Abstraction

Step back from pointers and the abstraction emerges. An ordered set is a collection of distinct elements that supports:

membership - is x in the set?
insert / delete - add or remove x, preserving order
order queries - minimum, maximum, the element just larger than x (successor), the element just smaller (predecessor)
range queries - all elements in [lo, hi], or how many there are

A hash set gives O(1) membership but has no order - it cannot answer successor, predecessor, or range queries at all. A sorted array gives fast order and range queries but O(n) insertion and deletion (shifting elements). A balanced BST gives all of them in O(log n) - that combination of fast membership and fast order/range operations under mutation is what makes the ordered set a distinct and essential tool.

Operation	Hash Set	Sorted Array	Balanced BST
Membership	O(1)	O(log n)	O(log n)
Insert / Delete	O(1)	O(n)	O(log n)
Min / Max	O(n)	O(1)	O(log n)
Successor / Predecessor	O(n)	O(log n)	O(log n)
Range query	O(n)	O(log n + k)	O(log n + k)
Maintains order	No	Yes (static)	Yes (dynamic)

Tip: The decision rule: if you only need membership, use a hash set - it's faster and simpler. The moment you need order - "what's the next booking after this time?", "how many prices are below X?", "give me everything between lo and hi while items keep arriving" - reach for an ordered set. The final three problems in this section (the calendar and stock-price problems) are pure ordered-set applications where this is the whole game.

What This Section Covers

The section moves from the raw operations outward to the abstraction:

Basic operations - search, and the search-flavored queries (closest value, two-sum, range sum) that exploit the ordering to prune.
Modification - trim, insert, delete, and recover (fix a BST where two nodes were swapped). Deletion is the genuinely tricky one and the heart of the section.
Navigation - successor and predecessor, and LCA on a BST (which the ordering makes far simpler than the general-tree version from the last section).
Construction - building a BST from a preorder sequence, converting a BST to a sorted doubly linked list, and finding the largest BST subtree inside an arbitrary tree.
Ordered-set applications - the calendar and stock-price problems, solved by reaching for an ordered map rather than a raw tree.

Throughout, the same instincts from the traversal section apply - recurse, act, combine - but now in service of a single goal: maintaining order under change. That is the one job an ordered set does that nothing else does as well, and it is the job that makes it ubiquitous in real systems.

The next topic, Search in a Binary Search Tree, is the operation everything else builds on: given a BST and a target value, return the subtree rooted at the matching node (or null). It is the BST invariant turned directly into code - compare, then go left or right - and it establishes the O(h) cost model and the recurse-or-iterate choice that recur in every operation throughout the section.

Back to DSA Mastery - Interview Prep, End to End