One ordering rule, held at every node — and every problem in this deck is a consequence of it.
18Problems
16Units
17Live walks
← → ↑ ↓ or W A S D navigateSPACE next DOUBLE-CLICK to advanceI index G goto problem P predictH hide solutions F fullscreen
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
02 / START HEREREAD THIS ONE FIRST
HOW THIS DECK WORKS
This is not a list of problems. It is 16 learning units, and every
one runs the same four beats. Go in order and the problems stop feeling random.
ASSUMEDBinary Trees, decks I–III. Every walk here is a traversal you already know; what is new is that the ordering lets you skip half of it.
01 INTROWhat the concept is, and what to watch for
02 WALKStep through it on a live tree, with the code beside it
03 DRILLS2 to 4 questions checking the walk landed
04 PROBLEMSThe problems that concept unlocks
Moving around
← ↑Back a slide — or A / W→ ↓Forward — or D / S / Space2×clickDouble-click the right side to advance, left to go back. A single click never moves the deck.IThe index: every problem, clickable, with your progressGJump straight to a problem by its numberFFullscreen
While you study
HHide solutions — blurs code and steps so you try firstPPredict mode: call the next step before the animation plays it☐ ★Mark solved, or star to revisit. Both are saved automatically.
18 PROBLEMS · 17 LINK TO A JUDGE · 1 IS A CONCEPT THE DRILLS COVER
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
03 / SIGNALSWHEN YOU SEE X, REACH FOR Y
READ THE STATEMENT, NAME THE WALK
A map to come back to. Every name on it is taught in its own unit.
“FIND / SEARCH / DOES IT EXIST” IN A BST
one comparison names a direction, and the other subtree is never looked at
WALK DOWN · no recursion neededO(h)
“SMALLEST ≥ X”, “LARGEST ≤ X”, “NEXT ONE AFTER X”
the answer may be a node you already walked past, so record it on the way down
CARRY A CANDIDATE · ceil / floor / successorO(h)
“Kth SMALLEST”, “VALIDATE”, “IS IT SORTED”
in-order of a BST emits sorted values, so the question is about a sorted list
IN-ORDER WITH STATE · a counter, or the previous valueO(n) worst, less if you can stop
“A PAIR SUMMING TO K”, “MERGE TWO TREES”
sorted input plus two ends is the two-pointer scan, and a tree can supply both
TWO ITERATORS · forward and reverseO(n) time, O(h) space
“INSERT”, “DELETE”, “BUILD FROM A TRAVERSAL”
the structure changes, and the ordering says where — nothing has to be searched for
RESTRUCTURE · a failed search names the slotO(h), or O(n) to build
“LARGEST SUBTREE THAT IS A BST”, “IS THIS A BST”
a node cannot be judged from itself, so facts have to travel up from both children
POST-ORDER TUPLE · min, max, size, verdictO(n)
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
04 / CONSTRAINTSBEFORE YOU WRITE A LINE
READ THE ANSWER OFF THE CONSTRAINTS
Skim now, return after unit 02.
n ≤
BUDGET
WHAT THAT BUYS YOU
n ≤ 10³
O(n²)
check every subtree separately: correct and slow, and unit 16 shows the fast way
n ≤ 10⁵
O(n)
one traversal, doing all the work on the way past. Validate, kth, recover, merge
n ≤ 10⁵
O(h) per query
the home row for this deck: search, insert, delete, ceil, floor, LCA, successor
h ≈ log n
O(log n)
what O(h) BECOMES on a balanced tree — 10⁵ nodes is 17 comparisons
h = n
O(n) per query
the same code on sorted input: a chain, and every O(h) claim above collapses
The last row is sorted input: a plain BST does not rebalance, so h becomes n.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
05 / ROADMAPWHAT YOU ARE ABOUT TO DO
THE WHOLE RUN, 16 UNITS
Sixteen units. Units 02 to 06 walk down the tree; unit 07 shows in-order is sorted, and later units build on it.
UNIT 01
WHAT A BST IS
3 DRILLS1 PROBLEM
UNIT 02
WALK, DO NOT SEARCH
3 DRILLS2 PROBLEMS
UNIT 03
CEIL — CARRY A CANDIDATE
3 DRILLS1 PROBLEM
UNIT 04
FLOOR — THE MIRROR
2 DRILLS1 PROBLEM
UNIT 05
INSERT WITHOUT RESTRUCTURING
3 DRILLS1 PROBLEM
UNIT 06
DELETE — THE THREE CASES
3 DRILLS1 PROBLEM
UNIT 07
INORDER IS SORTED
3 DRILLS1 PROBLEM
UNIT 08
VALIDATE BY RANGE
3 DRILLS1 PROBLEM
UNIT 09
LCA IS THE SPLIT POINT
3 DRILLS1 PROBLEM
UNIT 10
BUILD FROM PREORDER
3 DRILLS2 PROBLEMS
UNIT 11
SUCCESSOR WITHOUT A PARENT
3 DRILLS1 PROBLEM
UNIT 12
THE CONTROLLED STACK
3 DRILLS1 PROBLEM
UNIT 13
MERGE TWO SORTED WALKS
2 DRILLS1 PROBLEM
UNIT 14
TWO SUM, BOTH ENDS
3 DRILLS1 PROBLEM
UNIT 15
RECOVER — TWO VIOLATIONS
3 DRILLS1 PROBLEM
UNIT 16
LARGEST BST INSIDE A TREE
3 DRILLS1 PROBLEM
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
06 / INDEXPRESS I FROM ANYWHERE
INDEX — ALL 18 PROBLEMS
Click any problem to jump straight to it. Solved ones turn green. Press
I from anywhere to come back here. The number is the problem's
fixed number in this deck, not a slide position.
Basics · 03
Practice Problems · 13
Extras · 02
SOLVEDHAS A JUDGE LINKCONCEPT — DRILLS ONLY
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
07 / INTROUNIT 01 · WHAT A BST IS
UNIT 01 — WHAT A BST IS
One ordering rule, held over subtrees rather than over children
THE QUESTION THIS UNIT ANSWERS
WHAT DOES ORDERING BUY YOU THAT A BINARY TREE DOES NOT HAVE?
BST propertysubtreeheight hin-order
WHAT TO LOOK FOR
01THE RULE IS ABOUT EVERYTHING ON EACH SIDE, NOT THE TWO CHILDREN
02NO TWO NODES HOLD THE SAME VALUE · THERE IS NO EQUAL CASE
03READ THE TREE LEFT TO RIGHT — IT COMES OUT SORTED
04EVERY BOUND IN THIS DECK IS O(h) · h IS log n ONLY IF IT IS BALANCED
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
08 / MECHANISMUNIT 01 · ANATOMY · CODE MIRRORED
ONE RULE, AND IT IS NOT ABOUT CHILDREN
The rule is about subtrees: everything on the left is smaller, everything on the right is larger. Read left to right, the values come out sorted.
THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
09 / DRILLUNIT 01 · WHAT A BST IS · 1 OF 2
CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?
DRILL 01 · RECALL
Smaller goes left and larger goes right. What does the rule leave for a value equal to the node?
No equality at all. Left is strictly smaller and right is strictly larger, so an equal value has no legal side.
DRILL 02 · RECALL
The rule is stated over everything on each side, not over the two children. Why does that distinction matter?
It separates a correct validator from a wrong one. A node can fit its parent yet sit in the wrong half of an ancestor.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
10 / DRILLUNIT 01 · WHAT A BST IS · 2 OF 2
CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?
DRILL 01 · TRANSFER
A new value walks down from the root, left if smaller and right if larger, and is attached at the first empty spot. Insert 1, 2, 3, 4, 5 in that order. What have you built?
A linked list. Every value is larger than the last, so every insertion goes right and the height is n.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
11 / CONCEPT#01 · CONCEPT · EASY
Introduction to BST
EASYconceptCONCEPT · NO LEETCODE · DRILLS COVER IT
SIGNAL — WHAT GIVES IT AWAY
A concept — the definition itself, and the two ways it is misread
INTUITION
The rule covers whole subtrees, not just the two children.
STEPS
Left subtree: EVERY value is smaller than the node
Right subtree: EVERY value is larger than the node
No equality — a duplicate has no legal side unless the problem names one
Both subtrees are themselves BSTs, all the way down
Therefore in-order emits the values in sorted order
BRUTE—
→
OPTIMAL—
↕ SCROLL
// the property, stated the way it is actually used// left subtree : every value < node->val// right subtree : every value > node->val// and both subtrees are themselves BSTs//// consequence: in-order traversal emits sorted values.
# the property, stated the way it is actually used# left subtree : every value < node.val# right subtree : every value > node.val# and both subtrees are themselves BSTs## consequence: in-order traversal emits sorted values.
TIME—definition, not an algorithm
SPACE—nothing is stored
TRAP
“Left child smaller, right child larger” is weaker, and accepts trees that are not BSTs.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
12 / WARMUPAFTER UNIT 01 · 1 OF 2
WHAT THE ORDERING ACTUALLY PROMISES
DRILL 01 · RECALL
A BST is not the same claim as “each node's two children are ordered”. What is the actual rule?
The rule is about whole subtrees. Checking only the two children passes invalid trees.
DRILL 02 · RECALL
Why is every complexity in this deck written O(h) rather than O(log n)?
Nothing keeps it balanced. Sorted inserts build a chain, and every walk becomes O(n).
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
13 / WARMUPAFTER UNIT 01 · 2 OF 2
WHAT THE ORDERING ACTUALLY PROMISES
DRILL 01 · TRACE
In-order traversal of a BST gives you what, and why does it matter here?
Sorted. Left is smaller, right is larger, so left, node, right reads in order.
DRILL 02 · BUG
Searching a BST. One line makes this an O(n) traversal of a structure built to avoid exactly that. Which?
It never uses the order. It finds the key, but visits every node: O(n).
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
14 / INTROUNIT 02 · WALK, DO NOT SEARCH
UNIT 02 — WALK, DO NOT SEARCH
A search that throws away half the remaining tree at every step
THE QUESTION THIS UNIT ANSWERS
HOW DOES ONE COMPARISON DELETE AN ENTIRE SUBTREE?
O(h)leftmostrightmostdiscard
WHAT TO LOOK FOR
01THE OPPOSITE SUBTREE IS NOT REJECTED — IT IS NEVER VISITED
02A BINARY TREE WOULD NEED A FULL TRAVERSAL: O(n) AGAINST O(h)
03MIN AND MAX NEED NO COMPARISON, ONLY A DIRECTION
04THE MINIMUM MAY STILL HAVE A RIGHT CHILD — IT IS NOT A LEAF
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
15 / MECHANISMUNIT 02 · BSTSEARCH · CODE MIRRORED
EVERY COMPARISON DELETES HALF THE REMAINING TREE
Each comparison picks a side and the other subtree is never looked at. That is O(h): log n if balanced, n if built from sorted input.
THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
16 / MECHANISMUNIT 02 · BSTMINMAX · CODE MIRRORED
THE ONLY TWO QUERIES THAT COMPARE NOTHING
Go left until there is no left: that is the minimum. It is not always a leaf, since it can have a right child.
THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
17 / DRILLUNIT 02 · WALK, DO NOT SEARCH · 1 OF 2
CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?
DRILL 01 · RECALL
A plain binary tree has no ordering. To find a value in one, what are you forced to do?
Any full traversal: O(n). With no ordering, nothing tells you which way to go.
DRILL 02 · TRACE
A list in brackets gives a tree level by level, left to right: 8 is the root, 4 and 12 its children, 2 and 6 under 4, 10 and 14 under 12, then 1 3 under 2 and 5 7 under 6. In the tree [8,4,12,2,6,10,14,1,3,5,7], searching for 7 — how many nodes does the walk look at, and how many does it skip?
Four looked at, seven skipped. The walk is 8 → 4 → 6 → 7.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
18 / DRILLUNIT 02 · WALK, DO NOT SEARCH · 2 OF 2
CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?
DRILL 01 · BUG
Finding the minimum of a BST. One line is wrong. Which?
Search for the value. It ends at a null, and that null is where the value goes. Nothing else moves.
STEPS
The value is promised not to be in the tree, so the equal case never happens
If the tree is empty, the new node is the root
Walk down comparing, exactly as a search would
When the child on the chosen side is null, attach there
Return the root, unchanged in identity
BRUTEO(n) rebuilding the tree
→
OPTIMALO(h)
↕ SCROLL
Node* insertIntoBST(Node* root, int val) {
if (!root) return new Node(val);
Node* cur = root;
while (true) {
if (val < cur->val) {
if (!cur->left) { cur->left = new Node(val); break; }
cur = cur->left;
} else {
if (!cur->right) { cur->right = new Node(val); break; }
cur = cur->right;
}
}
return root;
}
// the same insert, recursive: each call RETURNS its subtree's root,// and the parent stores it
Node* insert(Node* root, int val) {
if (!root) return new Node(val);
if (val < root->val) root->left = insert(root->left, val);
else root->right = insert(root->right, val);
return root;
}
def insertIntoBST(root, val):
ifnot root: return TreeNode(val)
cur = root
whileTrue:
if val < cur.val:
ifnot cur.left:
cur.left = TreeNode(val); break
cur = cur.left
else:
ifnot cur.right:
cur.right = TreeNode(val); break
cur = cur.right
return root
# the same insert, recursive: each call RETURNS its subtree's root,# and the parent stores itdef insert(root, val):
ifnot root: return TreeNode(val)
if val < root.val: root.left = insert(root.left, val)
else: root.right = insert(root.right, val)
return root
TIMEO(h)the search walk, plus one link
SPACEO(1)iterative
TRAP
Assigning to a copy.root = new Node(v) on a by-value pointer changes nothing. Return the new root.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
35 / INTROUNIT 06 · DELETE — THE THREE CASES
UNIT 06 — DELETE — THE THREE CASES
Three cases, and only the third is a real problem
THE QUESTION THIS UNIT ANSWERS
WHAT REPLACES A NODE THAT HAS TWO CHILDREN?
successorsplicetwo-child case
WHAT TO LOOK FOR
01CASE 1, A LEAF: UNHOOK IT · CASE 2, ONE CHILD: THE CHILD MOVES UP
02TWO CHILDREN: COPY THE IN-ORDER SUCCESSOR'S VALUE IN
03THE SUCCESSOR IS THE NEXT LARGER VALUE · HERE, THE LEFTMOST OF THE RIGHT SUBTREE
04THE SUCCESSOR HAS NO LEFT CHILD, SO REMOVING IT IS CASE 1 OR CASE 2
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
36 / MECHANISMUNIT 06 · BSTDELETE · CODE MIRRORED
TWO OF THE THREE CASES ARE NOT DELETION AT ALL
Leaf: unhook. One child: it moves up. Two children: copy in the successor's value, then delete the successor, which has no left child.
THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
37 / DRILLUNIT 06 · DELETE — THE THREE CASES · 1 OF 2
CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?
DRILL 01 · RECALL
Deleting a node with two children. Which value replaces it?
The in-order successor. The smallest value of the right subtree fits the hole.
DRILL 02 · TRANSFER
Why is the two-child case not actually the hardest thing here?
It becomes an easy case. The successor is the leftmost of the right subtree, so it has no left child.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
38 / DRILLUNIT 06 · DELETE — THE THREE CASES · 2 OF 2
CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?
DRILL 01 · BUG
The two-child branch of delete. One line is wrong. Which?
else {
Node* s = root->right;
while(s->right) s = s->right;
root->val = s->val;
root->right = deleteNode(root->right, s->val);
}
It finds the maximum of the right subtree, not the minimum.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
In-order is sorted, so the kth node visited is the kth smallest. Stop as soon as the counter reaches k.
STEPS
Walk in-order: left subtree, node, right subtree
Increment a counter as each node is visited
When the counter equals k, that node is the answer
Stop — the nodes after it are never counted
For kth largest, reverse the walk to right-node-left
BRUTEO(n log n) collect and sort
→
OPTIMALO(h + k)
↕ SCROLL
void kth(Node* n, int k, int& cnt, int& ans) {
if (!n || ans != -1) return;
kth(n->left, k, cnt, ans);
if (++cnt == k) { ans = n->val; return; }
kth(n->right, k, cnt, ans);
}
int kthSmallest(Node* root, int k) {
int cnt = 0, ans = -1; // -1 means not found yet
kth(root, k, cnt, ans);
return ans;
}
def kthSmallest(root, k):
st, cur = [], root
while st or cur:
while cur:
st.append(cur); cur = cur.left
cur = st.pop()
k -= 1if k == 0: return cur.val
cur = cur.right
TIMEO(h + k)h to walk down to the smallest, then k counts
SPACEO(h)the recursion stack
TRAP
A local counter. It resets in every subtree. Pass it by reference or keep it as a member.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
45 / INTROUNIT 08 · VALIDATE BY RANGE
UNIT 08 — VALIDATE BY RANGE
Every node carries a window, and a parent alone cannot supply it
THE QUESTION THIS UNIT ANSWERS
WHY DOES COMPARING EACH NODE TO ITS CHILDREN NOT WORK?
rangewindowstrictly increasing
WHAT TO LOOK FOR
01THE COUNTEREXAMPLE PASSES A PARENT-ONLY CHECK AND IS NOT A BST
02EACH NODE NARROWS THE RANGE ITS SUBTREES MAY USE
03THE ALTERNATIVE IS AN IN-ORDER THAT MUST STRICTLY INCREASE
04INT_MIN AS A BOUND REJECTS A TREE THAT CONTAINS IT
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
For a BST, preorder alone fixes the tree. Each call carries an upper bound and returns as soon as the next value exceeds it.
STEPS
Keep a shared index into the preorder array
Each call takes the next value only if it is under its bound
Build the left subtree with the bound tightened to this node
Build the right subtree with the bound inherited from the caller
A rejected value is NOT consumed, so the caller picks it up
BRUTEO(n²) inserting each from the root
→
OPTIMALO(n)
↕ SCROLL
Node* build(vector<int>& pre, int& i, int bound) {
if (i == pre.size() || pre[i] > bound) return nullptr;
Node* n = new Node(pre[i++]);
n->left = build(pre, i, n->val);
n->right = build(pre, i, bound);
return n;
}
Node* bstFromPreorder(vector<int>& pre) {
int i = 0;
return build(pre, i, INT_MAX);
}
def bstFromPreorder(pre):
i = 0def build(bound):
nonlocal i
if i == len(pre) or pre[i] > bound: returnNone
n = TreeNode(pre[i]); i += 1
n.left = build(n.val)
n.right = build(bound)
return n
return build(float('inf'))
TIMEO(n)every value taken once
SPACEO(h)the recursion stack
TRAP
Advancing past a rejected value. Move the index only when a value is taken.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
“next() and hasNext() over a BST, in sorted order” — with O(h) memory
INTUITION
An in-order walk you can pause. The stack holds a left spine; next() pops one and pushes the left spine of its right child.
STEPS
Constructor: push the root and everything down its left edge
next(): pop the top node; it is the smallest value not yet returned
Push its right child and everything down that child's left edge
Return the popped value
hasNext(): the stack is not empty
BRUTEO(n) memory, flattening the tree first
→
OPTIMALO(1) amortised
↕ SCROLL
class BSTIterator {
stack<Node*> st;
void pushLeft(Node* n) { // n and everything down its left edgewhile (n) { st.push(n); n = n->left; }
}
public:
BSTIterator(Node* root) { pushLeft(root); }
int next() {
Node* n = st.top(); st.pop(); // smallest value not yet returned
pushLeft(n->right); // what it still owed: its right sidereturn n->val;
}
bool hasNext() { return !st.empty(); }
};
class BSTIterator:
def __init__(self, root):
self.st = []
self._push_left(root)
def _push_left(self, n): # n and everything down its left edgewhile n:
self.st.append(n); n = n.left
def next(self):
n = self.st.pop() # smallest value not yet returned
self._push_left(n.right) # what it still owed: its right sidereturn n.val
def hasNext(self):
return bool(self.st)
TIMEO(1) amortisedeach node is pushed once and popped once
SPACEO(h)one root-to-leaf path at most
TRAP
Calling next() O(h). Each node is pushed once, so on average it is O(1).
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
71 / INTROUNIT 13 · MERGE TWO SORTED WALKS
UNIT 13 — MERGE TWO SORTED WALKS
Two BSTs are two sorted sequences, and you already know how to merge those
THE QUESTION THIS UNIT ANSWERS
CAN YOU MERGE TWO BSTs WITHOUT BUILDING A THIRD TREE?
mergetwo sorted listsiterator
WHAT TO LOOK FOR
01NOTHING NEW TO LEARN HERE: UNIT 07 PLUS UNIT 12
02IN-ORDER OF EACH TREE IS ALREADY SORTED
03THE ARRAY VERSION IS O(n+m) TIME AND O(n+m) SPACE
04TWO ITERATORS KEEP THE TIME AND DROP THE SPACE TO O(h1+h2)
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
72 / MECHANISMUNIT 13 · BSTMERGE · CODE MIRRORED
TWO SORTED SEQUENCES, WHICH YOU ALREADY KNOW HOW TO MERGE
Two BSTs are two sorted lists. Merge them with two iterators: same time as arrays, space only O(h1+h2).
THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
73 / DRILLUNIT 13 · MERGE TWO SORTED WALKS
CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?
DRILL 01 · RECALL
In-order is sorted. Given that, what does merging two BSTs reduce to?
The merge step of merge sort. Two BSTs are two sorted sequences.
DRILL 02 · TRANSFER
Collecting both in-orders into arrays and merging is O(n+m) time. What does driving two iterators instead buy?
Space, not time. Both are O(n+m) time; iterators keep only the two heights.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
Two BSTs are two sorted lists: merge them like merge sort. Two iterators keep the space at the two heights.
STEPS
Open an iterator on each tree
Repeatedly take the smaller of the two current heads
When one runs out, drain the other
The output is sorted by construction — nothing is sorted
BRUTEO((n+m)log(n+m)) concatenate and sort
→
OPTIMALO(n+m)
↕ SCROLL
// BSTIterator from problem #17, plus one method:// int peek() { return st.top()->val; } // next value, not removedvector<int> getAllElements(Node* a, Node* b) {
BSTIterator x(a), y(b);
vector<int> out;
while (x.hasNext() && y.hasNext())
out.push_back(x.peek() <= y.peek() ? x.next() : y.next());
while (x.hasNext()) out.push_back(x.next());
while (y.hasNext()) out.push_back(y.next());
return out;
}
def getAllElements(root1, root2):
def push(st, n):
while n: st.append(n); n = n.left
s1, s2, out = [], [], []
push(s1, root1); push(s2, root2)
while s1 or s2:
s = s1 if (not s2 or (s1 and s1[-1].val <= s2[-1].val)) else s2
n = s.pop()
out.append(n.val); push(s, n.right)
return out
TIMEO(n+m)every value touched once
SPACEO(h1+h2)two left spines
TRAP
Inserting one tree into the other. Slower, and it rebuilds what you already had.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
75 / INTROUNIT 14 · TWO SUM, BOTH ENDS
UNIT 14 — TWO SUM, BOTH ENDS
Two pointers, where the array is a tree
THE QUESTION THIS UNIT ANSWERS
HOW DO YOU FIND TWO VALUES THAT SUM TO K WITHOUT STORING THE TREE?
two pointersreverse iteratordistinct
WHAT TO LOOK FOR
01TWO SUM: DO ANY TWO VALUES ADD UP TO K? HERE THEY ARRIVE SORTED
02TWO DISTINCT ELEMENTS: THE POINTERS MUST NEVER MEET
03REMEMBERING EVERY VALUE SEEN (A HASH SET) WORKS AND COSTS O(n) SPACE
04FORWARD AND REVERSE ITERATORS ARE THE TWO ENDS OF A SORTED ARRAY
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
76 / MECHANISMUNIT 14 · BSTTWOSUM · CODE MIRRORED
TWO POINTERS, ON A TREE
Forward and reverse iterators are the two ends of a sorted list. Too small: move low up. Too big: move high down. Stop when a == b.
THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
77 / DRILLUNIT 14 · TWO SUM, BOTH ENDS · 1 OF 2
CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?
DRILL 01 · RECALL
The problem puts one condition on the pair. Which?
Two distinct elements. So loop while a < b; with <= a value pairs with itself.
DRILL 02 · TRACE
Sorted values 2 4 6 8 10 12 14, target 20. The low end is on 2 and the high end on 14: sum 16. What moves?
The low end moves up. The sum is too small, so only a larger low value can help.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
78 / DRILLUNIT 14 · TWO SUM, BOTH ENDS · 2 OF 2
CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?
DRILL 01 · TRANSFER
Remembering every value seen in a hash set also solves this in O(n) time. What does the two-iterator version do better?
Space. The set works, but ignores that the values are already sorted.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
79 / PROBLEM#14 · INORDER · EASY
Two Sum In BST | Check if there exists a pair with Sum K
Two Sum on sorted values. A forward and a reverse iterator are the two ends: too small, move low up; too big, move high down.
STEPS
Open a forward iterator (smallest first) and a reverse one
Take one value from each end
Sum too small: advance the low end
Sum too large: retreat the high end
Equal: found. Pointers crossing: no such pair
BRUTEO(n) time and O(n) space with a hash set
→
OPTIMALO(n)
↕ SCROLL
class BSTIterator {
stack<Node*> st; bool rev;
void pushAll(Node* n) {
while (n) { st.push(n); n = rev ? n->right : n->left; }
}
public:
BSTIterator(Node* root, bool reverse) : rev(reverse) { pushAll(root); }
int next() {
Node* n = st.top(); st.pop();
pushAll(rev ? n->left : n->right);
return n->val;
}
};
bool findTarget(Node* root, int k) {
BSTIterator lo(root, false), hi(root, true);
int a = lo.next(), b = hi.next();
while (a < b) {
if (a + b == k) returntrue;
if (a + b < k) a = lo.next();
else b = hi.next();
}
returnfalse;
}
def findTarget(root, k):
vals = []
def ino(n):
ifnot n: return
ino(n.left); vals.append(n.val); ino(n.right)
ino(root)
i, j = 0, len(vals) - 1while i < j:
s = vals[i] + vals[j]
if s == k: returnTrueif s < k: i += 1else: j -= 1returnFalse
TIMEO(n)each value passed once
SPACEO(h)two left spines
TRAP
Using a <= b. Then a value can pair with itself.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
80 / INTROUNIT 15 · RECOVER — TWO VIOLATIONS
UNIT 15 — RECOVER — TWO VIOLATIONS
A sorted sequence with two elements swapped falls in at most two places
THE QUESTION THIS UNIT ANSWERS
HOW MANY PLACES CAN A TWO-NODE SWAP SHOW UP IN AN IN-ORDER WALK?
dipadjacent swapprev pointer
WHAT TO LOOK FOR
01THE GUARANTEE IS EXACTLY TWO NODES, SWAPPED
02FAR APART GIVES TWO DIPS; ADJACENT GIVES ONE
03TWO DIPS: FIRST OF THE FIRST, SECOND OF THE LAST
04HANDLING ONLY THE TWO-DIP CASE IS THE STANDARD BUG
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
In-order should only rise. Far apart: two dips, take the first's first and the last's second. Adjacent: one dip holds both.
STEPS
Walk in-order, remembering the previously visited node
A value smaller than the previous one is a dip
First dip: record the previous node as first, this one as second
Any later dip: overwrite second with this node
Swap the values in first and second
BRUTEO(n log n) sort and compare
→
OPTIMALO(n)
↕ SCROLL
Node *first = nullptr, *second = nullptr, *prev = nullptr;
void inorder(Node* n) {
if (!n) return;
inorder(n->left);
if (prev && n->val < prev->val) {
if (!first) { first = prev; second = n; }
else second = n;
}
prev = n;
inorder(n->right);
}
void recoverTree(Node* root) {
inorder(root);
swap(first->val, second->val);
}
def recoverTree(root):
first = second = prev = Nonedef ino(n):
nonlocal first, second, prev
ifnot n: return
ino(n.left)
if prev and n.val < prev.val:
ifnot first: first, second = prev, n
else: second = n
prev = n
ino(n.right)
ino(root)
first.val, second.val = second.val, first.val
TIMEO(n)one in-order pass
SPACEO(h)the recursion stack
TRAP
Handling only two dips. Adjacent swaps give one dip, and the second pointer stays null.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
85 / INTROUNIT 16 · LARGEST BST INSIDE A TREE
UNIT 16 — LARGEST BST INSIDE A TREE
A parent cannot judge itself until both children have reported
THE QUESTION THIS UNIT ANSWERS
WHY MUST THIS BE POST-ORDER, AND WHAT HAS TO TRAVEL UPWARD?
post-ordertuplemin/max/size
WHAT TO LOOK FOR
01THE WHOLE TREE CAN FAIL ON A NODE THAT IS FINE WITH ITS OWN PARENT
02EACH CALL RETURNS MIN, MAX, SIZE AND VERDICT
03A NODE ROOTS A BST IFF BOTH CHILDREN DO AND IT FITS BETWEEN THEM
04VALIDATING EVERY SUBTREE SEPARATELY IS O(n²)
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
“Largest subtree that is a BST” — inside a tree that is not one
INTUITION
A node needs its children's min, max, size and verdict before it can judge itself, so this is postorder.
STEPS
Recurse into both children first
A null subtree is a BST of size 0. Its min is +inf and its max is -inf, so it never blocks its parent
This node roots a BST iff both children do AND its value fits between them
If so, its size is left + right + 1 — update the best
If not, return ok = false; every ancestor then fails too, and best keeps the largest size seen
BRUTEO(n²) validating every subtree
→
OPTIMALO(n)
↕ SCROLL
struct Info { int mn, mx, size; bool ok; }; // four facts about one subtree
Info go(Node* n, int& best) {
if (!n) return { INT_MAX, INT_MIN, 0, true }; // empty: min +inf, max -inf,// so both tests below pass
Info l = go(n->left, best), r = go(n->right, best);
if (l.ok && r.ok && n->val > l.mx && n->val < r.mn) {
int sz = l.size + r.size + 1;
best = max(best, sz);
return { min(n->val, l.mn), max(n->val, r.mx), sz, true };
}
return { 0, 0, 0, false }; // not a BST: parents read only ok
}
int largestBst(Node* root) { int best = 0; go(root, best); return best; }
def largestBSTSubtree(root):
best = 0def go(n):
nonlocal best
ifnot n: return (float('inf'), float('-inf'), 0, True)
lmn, lmx, lsz, lok = go(n.left)
rmn, rmx, rsz, rok = go(n.right)
if lok and rok and lmx < n.val < rmn:
sz = lsz + rsz + 1
best = max(best, sz)
return (min(n.val, lmn), max(n.val, rmx), sz, True)
return (0, 0, 0, False) # not a BST: parents read only ok
go(root)
return best
TIMEO(n)each node visited once
SPACEO(h)the recursion stack
TRAP
Returning only true or false. The parent needs the children's min and max too.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
90 / RECALLRETRIEVAL, NOT RECOGNITION · 1 OF 3
NAME THE WALK FROM WHAT IS ASKED
DRILL 01 · RECALL
A problem says “return the smallest value greater than or equal to X”. Which shape?
Carry a candidate. The key may be absent, so the answer is the last node that qualified.
DRILL 02 · RECALL
Which of these genuinely requires post-order rather than any other traversal?
Largest BST subtree. A node waits for its children's min, max, size and verdict: postorder.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
91 / RECALLRETRIEVAL, NOT RECOGNITION · 2 OF 3
NAME THE WALK FROM WHAT IS ASKED
DRILL 01 · TRANSFER
Given a BST and a target k, you must decide if two distinct nodes sum to k. Which costs least space?
Two iterators, O(h) space. An array or a hash set is O(n).
DRILL 02 · RECALL
Deleting a node with two children, you copy the in-order successor's value up. What must happen next?
Delete the successor. Its value now lives in the node, and it has no left child, so it is an easy case.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
92 / RECALLRETRIEVAL, NOT RECOGNITION · 3 OF 3
NAME THE WALK FROM WHAT IS ASKED
DRILL 01 · TRANSFER
You must return values in sorted order but the caller may stop at any point. Which design?
The controlled stack. It holds one left spine, O(h).
DRILL 02 · RECALL
Which single fact does the biggest share of this deck rest on?
In-order is sorted. Six of the eighteen problems are that one fact.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
93 / TRAPSPLAUSIBLE, WRONG, AND SILENT
SIX WAYS TO BE PLAUSIBLY WRONG
None of these crash. Each returns something that looks like an answer. That is what makes them expensive.
THE VALIDATOR THAT ONLY LOOKS AT CHILDREN
Checking node->left->val < node->val passes trees that are not BSTs. A node must fit every ancestor: carry a window down.
INT_MIN AS A SENTINEL BOUND
INT_MIN and INT_MAX as bounds reject a valid tree that holds those values. Use long long bounds.
THE MINIMUM IS NOT A LEAF
The minimum has no left child, but it can have a right one. Stop at !node->left, not at a leaf.
RECORDING THE CANDIDATE THEN WALKING THE WRONG WAY
In ceil, a qualifying node means go LEFT for something smaller. Floor is the mirror: flip the comparison and the direction together.
THE Kth COUNTER DECLARED INSIDE THE RECURSION
A local counter resets in every subtree, so ++cnt == k only fires for k = 1. Pass it by reference.
RECOVER THAT ONLY HANDLES TWO DIPS
Swapped nodes far apart give two dips; adjacent ones give ONE. Handle both, or the smallest test fails.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
94 / CHEATSHEETREVISION SURFACE
ONE SCREEN, THE WHOLE DECK
Every operation in this deck with its cost and the one line that selects it. This is the night-before page.
ALGORITHM
TIME
SPACE
REACH FOR IT WHEN
Search / insert
O(h)
O(1) iterative
one comparison per level; insert is the search that ended in a null
Find min / max
O(h)
O(1)
walk left (or right) until you cannot — no comparison at all
Ceil / floor / successor
O(h)
O(1)
record the last node that qualified, then keep hunting tighter
Delete
O(h)
O(h) recursive
0 or 1 child unhooks; 2 children copies the successor up and deletes it
Kth smallest
O(h + k)
O(h)
in-order with a counter, and stop the moment it reaches k
Validate
O(n)
O(h)
a window per node, or an in-order that must strictly increase
LCA
O(h)
O(1) iterative
walk while both agree; the first disagreement IS the answer
Build from preorder
O(n)
O(h)
one pass with an upper bound — the bound marks where a subtree ends
BST iterator
O(1) amortised
O(h)
a stack holding only the left spine of what has not been returned
Merge two BSTs
O(n+m)
O(h1+h2)
two iterators, merged as two sorted sequences
Two sum
O(n)
O(h)
forward and reverse iterators as the two ends of a sorted array
Recover
O(n)
O(h)
in-order; two dips means far apart, one dip means adjacent
Largest BST subtree
O(n)
O(h)
post-order returning min, max, size and verdict from each child
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
95 / CLOSE14 · BINARY SEARCH TREES
THE ORDERING IS THE ALGORITHM
One promise at every node: left is smaller, right is larger. Walks go down one side; in-order reads it sorted. Next is graphs, where nothing is ordered.
16 units, 18 problems, 17 live walks. Every walk shows values the build worked out and checked.
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
■ TOO SMALL TO READ
1280×720
INVARIANT · 14 · BINARY SEARCH TREES
This one needs a laptop
Not a preference — an arithmetic one. Every slide is a fixed
1280 × 720 stage: a graph animating beside the code that drives it, with
the problems laid out two columns wide. It scales as a single piece, so on a
screen this size the body text comes out around
4px tall.
Shrinking it further would not help, and rebuilding it to reflow would mean
losing the thing that makes it worth reading.
YOUR SCREEN0 × 0
NEEDED1060 × 610
WHAT IS WAITING ON THE LAPTOP
Algorithms you can step through, forwards and back
Predict mode — call the next step before it is shown
Spaced repetition, so the sheet stops decaying
WATCH IT RUN, THEN RUN IT FROM MEMORY Your progress is saved per device, so anything you
tick on the laptop will be waiting there.