What you will learn
The BST invariant and why it forces every operation into O(h) time
Recursive and iterative search, minimum, maximum, lower bound, and upper bound
Insertion and the three-case deletion (leaf, one child, two children with inorder successor)
The four BST patterns: sorted traversal, reversed sorted traversal, range postorder, and two pointer
Lowest common ancestor on a BST in O(h) using only the ordering property
How to design forward and reverse iterators with amortised O(1) next() and O(h) stack space
Why this course
The BST invariant fits in one sentence. Every value in a node's left subtree is smaller than the node, every value in its right subtree is larger. That single rule is why an inorder walk produces sorted output, why search runs in O(log N) on a balanced tree, and why a tree built by inserting [1, 2, 3, 4, 5] in order degrades to O(N) because the invariant is technically satisfied by a stick-shaped tree too. The definition is one sentence. The consequences fill a whole course.
This course rebuilds your understanding of binary search trees from the ordering property up, then walks through the four traversal patterns that solve almost every BST interview question. You finish by implementing the forward and reverse BST iterators with amortised O(1) next() calls, the construct that makes the two-pointer pattern on a tree possible.
Requirements
The course assumes basic programming and recursion comfort, but reintroduces the tree concepts it depends on.
- Ability to read tree code (nodes with
leftandrightpointers) in at least one language. - Familiarity with Big-O including the gap between O(log N) and O(N).
- Some exposure to recursion is helpful; the binary tree course pairs well but is not required.
Overview
A binary search tree is the simplest data structure where ordering and structure interlock. It is a binary tree with one extra rule, that every value in a node's left subtree is strictly less than the node and every value in its right subtree is strictly greater, and that single rule turns an unordered tree into a structure that supports search, insertion, deletion, range queries, and ordered iteration in time proportional to the tree's height. Java's TreeMap, C++'s std::set and std::map, and the ordered key-value containers in most mainstream languages are built on a balanced BST variant under the hood.
Representation of a binary tree
This course covers both halves of the problem: how the BST invariant turns into working code for every operation, and how to recognise which of the four traversal patterns a given problem fits.
Fundamentals
The course opens with the BST invariant itself. You see how the rule (left subtree below, right subtree above) propagates through every node, why the leftmost node is always the minimum, the rightmost always the maximum, and why an inorder walk visits values in ascending order while a reverse inorder walk visits them in descending order. Those four traits drive every BST algorithm that follows.
From there the course works through search, insertion, and deletion in both recursive and iterative forms. You meet the O(h) complexity bound that haunts every BST operation, then unpack what h actually is: O(log N) on a balanced tree and O(N) on a degenerate one that was inserted in sorted order. The height-balance section connects this to the balance factor (the difference between left and right subtree heights at every node) and explains why keeping a tree perfectly complete is impractical while keeping it height-balanced is what self-balancing trees actually maintain.
The fundamentals close with two operations that lean on the BST property without walking the whole tree: lowest common ancestor in O(h) by descending from the root until you hit the first node whose value sits between the two queries, and the iterator pattern, where a stack stores the path back to the root so next() returns the next inorder node in amortised O(1) time.
Problem solving
Once the operations are in place, the course shifts to patterns. A binary search tree gives you four traversal templates, and almost every BST interview problem reduces to one of them. After a few seconds of reading, you should be able to name which template the problem fits and the rest of the solution writes itself.
f and aggregating the results with g, all in O(N) time. Lowest Absolute Variance, BST Validator, BST to Sorted Array, BST to DLL.Each pattern is taught in three layers. An Understanding lesson works the technique on a problem where the pattern is obvious. An Identifying lesson then teaches you the signals (ascending output, descending output, range constraints, pair-sum framing) that tell you a new problem fits the template. Then four problems per pattern give you progressively harder applications. The course finishes with the forward and reverse iterator design, the data structure that makes the two-pointer pattern on a tree possible in the first place.
How this course is different
Most BST material online either stops at the definition with a single search example, or jumps straight to problem grinding without explaining why an inorder walk drives half the patterns. This course covers both halves seriously.
Who this course is for
The course suits anyone who needs to understand BSTs at the level required to recognise problems, not just recite the definition.
- Engineers who have learned binary trees but have not yet seen what the BST ordering invariant unlocks.
- Self-taught and bootcamp graduates who can implement BST search but stall on insert-with-balance or delete-with-two-children.
- Working developers who use
TreeMap,std::map, orstd::setdaily but have never opened up the underlying ordered tree. - Interview candidates preparing for FAANG and Big Tech onsites where validate-BST, kth-largest, range queries, LCA, and iterator design appear repeatedly.
- Returning engineers who learned BSTs years ago and want a clean refresher organised around the traversal patterns rather than disconnected problems.
- Engineers who can write an inorder traversal but cannot quickly explain why it produces sorted output on a BST and not on a generic binary tree.
Continue your DSA journey
A binary search tree sits at the intersection of trees, ordering, and search. The natural next steps depend on which side you want to deepen.
- Binary tree: A BST is a binary tree with one extra ordering rule. The binary tree course covers the generic traversal mechanics (preorder, inorder, postorder, level order, iterative variants) that the BST iterator builds on, plus LCA on arbitrary trees, where you cannot use the ordering shortcut taught here.
- Recursion: Every BST operation in this course is taught in both recursive and iterative forms. The recursion course's head, tail, multiple, and multidimensional recursion templates make those recursive walks feel natural rather than memorised, and explain why deletion's two-child case maps cleanly onto a multi-step recursion.
- Backtracking: Several BST problems generalise to backtracking on a search space where the BST property prunes one subtree per step. The backtracking course teaches the prune-and-recurse framework in full generality, which lets you transfer the BST patterns onto problems that are not literally trees.
- Sorting: A BST's inorder walk is sort by another name, and inserting sorted input into an empty BST runs the same comparisons as insertion sort. The sorting course gives you the comparison-based view (quicksort, mergesort) that makes the sorted-traversal pattern click harder.
- Searching: Binary search on a sorted array and BST search are the same idea on different memory layouts. The searching course's lower-bound and upper-bound variants map almost directly onto the recursive and iterative lower-bound and upper-bound searches covered here.
Frequently asked questions
TreeMap, C++ std::set, or any pointer-based implementation.h, not the node count N. On a balanced tree the height stays at O(log N) and operations run in O(log N) time. On a degenerate tree (for example, one built by inserting sorted input one element at a time) every node ends up with only a right child, the height grows to N - 1, and every operation becomes O(N), no better than scanning a linked list. Self-balancing variants like AVL and Red-Black trees exist to keep h at O(log N) under any sequence of inserts and deletes.