THE TREE
One ordering rule, held at every node — and every problem in this step is a consequence of it.
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.
16 PROBLEMS · 15 LINK TO A JUDGE · THE REST ARE CONCEPTS THE DRILLS COVER
Six phrasings cover every row in this step. The point is not that a BST is fast — it is that the ordering answers a question the search was going to ask, so the work becomes a walk instead of a traversal. The right-hand column is what each phrasing permits you to write.
one comparison names a direction, and the other subtree is never looked at
WALK DOWN · no recursion neededO(h)the answer may be a node you already walked past, so record it on the way down
CARRY A CANDIDATE · ceil / floor / successorO(h)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 stopsorted input plus two ends is the two-pointer scan, and a tree can supply both
TWO ITERATORS · forward and reverseO(n) time, O(h) spacethe 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 builda node cannot be judged from itself, so facts have to travel up from both children
POST-ORDER TUPLE · min, max, size, verdictO(n)Everything in this deck is written O(h), not O(log n), and the difference is the whole risk. Type a bound and the row it lands in rings gold.
The last row is the same code on sorted input: a plain BST does not rebalance, so h becomes n and every bound above it collapses. That is what AVL and red-black trees exist to prevent, and this sheet does not cover them.
A BST is not the same claim as “each node's two children are ordered”. What is the actual rule?
It quantifies over subtrees, not children. This is the single most expensive misunderstanding in the topic — it produces a validator that returns true on an invalid tree, which is LeetCode 98's whole point. A node has to beat every ancestor, not just its parent.
Why is every complexity in this deck written O(h) rather than O(log n)?
Nothing keeps a plain BST balanced. Insert sorted data and every value goes the same way, giving a chain of height n — and every walk in this deck becomes O(n). O(h) is the honest bound; O(log n) is what it becomes on a balanced tree, which is what AVL and red-black trees exist to guarantee.
In-order traversal of a BST gives you what, and why does it matter here?
Sorted. Left, node, right — and the ordering rule guarantees everything left is smaller. Nine of the sixteen problems in this deck are that one fact used differently: count to k, check it rises, find the dips, merge two of them, walk it from both ends. Recognising it is most of the work.
Searching a BST. One line makes this an O(n) traversal of a structure built to avoid exactly that. Which?
bool find(Node* root, int key){
if(!root) return false;
if(root->val == key) return true;
return find(root->left, key) || find(root->right, key);
}
It never compares to choose a direction. This is correct — it finds the key — and it is the binary-tree search, which visits every node. One comparison against root->val decides the side and discards the other subtree whole. Correct code that ignores its own data structure is the hardest kind of wrong to notice.
Sixteen units, fifteen lectures, 2h 52m. The first six are walks — search, ceil, floor, insert, delete. Unit 07 states the fact the rest of the deck runs on, and units 08–16 are that fact applied nine ways. Unit 12 has no sheet row and unit 13 has no lecture; both are explained where they appear.
Click any problem to jump straight to it. Solved ones turn green. Press I from anywhere to come back here. The number is the sheet's row, not your position — the deck teaches in the order that builds, so you will meet them slightly out of numerical sequence.
One ordering rule, held over subtrees rather than over children
WHAT DOES ORDERING BUY YOU THAT A BINARY TREE DOES NOT HAVE?
The lecture states the rule twice, and the second half is the part people drop. What does it say about equality?
No equality at all. The lecture is explicit that there is no presence of equal to in any case. Judges differ on duplicates — LeetCode 98 rejects them outright — so when a problem does allow them it will say so, and it will tell you which side they take. Assuming a side is how a correct-looking validator fails one hidden test.
The rule is stated over everything on each side, not over the two children. Why does that distinction matter?
It is the difference between a correct validator and a wrong one. A node can satisfy its parent and still sit in the wrong half of an ancestor — that is exactly the tree unit 08 is built around. The lecture says everything on the left, and it means the whole subtree.
Insert 1, 2, 3, 4, 5 into an empty BST 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. All the O(log n) claims in this deck assume a balanced tree, and a plain BST does nothing to keep itself balanced — that is what AVL and red-black trees are for, and why sorted input is the worst case rather than the best.
The definition people carry is left child smaller, right child larger, and it is wrong in a way that costs an hour on LeetCode 98. The rule is over subtrees: every value in the left subtree is smaller than the node, and every value in the right subtree is larger. A node must beat every ancestor, not just its parent. Step through and watch the window each node sits in — and notice the last slide, where reading the tree left to right gives you the values in sorted order. That is the same rule said once, and it is what the next fourteen units are built on.
A concept row — the definition itself, and the two ways it is misread
The rule is quantified over subtrees. That single word is the difference between a validator that works and one that returns true on an invalid tree, and it is why this row exists before any code does.
// 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.
“Left child smaller, right child larger” is a DIFFERENT and weaker claim. It accepts trees that are not BSTs, and it is the reason LeetCode 98 is a Medium.
A search that throws away half the remaining tree at every step
HOW DOES ONE COMPARISON DELETE AN ENTIRE SUBTREE?
The lecture opens by contrasting this with a binary tree. What would a binary tree force you to do?
Any full traversal — the point is that it is O(n). Without an ordering, no comparison tells you which way to go, so you have to be prepared to look at every node. The ordering is precisely what converts that walk into a decision, and the decision is what makes it O(h).
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. At every step the opposite subtree is discarded whole — not visited and rejected, never visited. That is the shape of the saving, and it is why the bench greys those nodes rather than hiding them.
Finding the minimum of a BST. One line is wrong. Which?
int findMin(Node* root){ while(root->left && root->right) root = root->left; return root->val; }
&& should be a test on the left child alone. The minimum is the leftmost node, and the leftmost node is allowed to have a right child. This loop stops as soon as either child is missing, so on a tree whose leftmost node has a right child it returns a value that is not the minimum — and returns it silently.
The greyed nodes are the point. At each step one comparison decides a direction, and the entire subtree on the other side is gone — not searched and rejected, never looked at. Eleven nodes, four comparisons. That is O(h), and on a balanced tree h = log n. The catch is the word balanced: a BST built from already-sorted input is a linked list, and this same walk becomes O(n).
Minimum and maximum need no target and no comparison at all — only a direction. Go left until there is no left, and you are standing on the smallest value in the tree. The mistake worth naming: the minimum is not necessarily a leaf. It cannot have a left child, but it may well have a right one, and code that tests isLeaf instead of !node->left is wrong on exactly that shape.
“Find the node with this value” — and the tree is a BST
One comparison per level names a direction, and the subtree on the other side is discarded whole. No recursion is needed: the walk never has to come back up, because it never has to reconsider.
Node* searchBST(Node* root, int val) { while (root && root->val != val) root = val < root->val ? root->left : root->right; return root; }
def searchBST(root, val): while root and root.val != val: root = root.left if val < root.val else root.right return root
Writing it as a binary-tree search — recursing into both subtrees — is CORRECT and O(n). It passes, and it throws away the only reason the structure exists.
“Smallest” or “largest” value in a BST, with no key given
These are the only two queries here that compare nothing at all. The smallest value is the one with no smaller value to its left, so walk left until there is no left.
int findMin(Node* root) { while (root->left) root = root->left; return root->val; } int findMax(Node* root) { while (root->right) root = root->right; return root->val; }
def find_min(root): while root.left: root = root.left return root.val def find_max(root): while root.right: root = root.right return root.val
The minimum is NOT necessarily a leaf. It cannot have a left child; it can have a right one. Looping while BOTH children exist stops early and returns the wrong value.
The answer may be a node the walk already passed
WHAT DO YOU RETURN WHEN THE KEY IS NOT IN THE TREE AT ALL?
Ceil of a key is the smallest value greater than or equal to it. Why can the walk not simply return where it stops?
The key need not be in the tree. Ceil is asked precisely when it is not, so the walk falls off the bottom and there is nothing to return there. The answer is a node the walk passed several steps earlier — which is why the candidate has to be recorded on the way down rather than recovered at the end.
Tree [8,4,12,2,6,10,14,1,3,5,7], ceil of 9. Which nodes does the walk stand on, and what is the answer?
8 → 12 → 10, and the answer is 10. 8 is too small so it cannot qualify; 12 qualifies and is recorded, then the walk goes left hunting something tighter; 10 qualifies and replaces it. The walk then runs out of tree, and the answer is the last thing recorded — not where it stopped.
Ceil, with the candidate carried. One line is wrong. Which?
int findCeil(Node* root, int key){ int ceil = -1; while(root){ if(root->val == key) return root->val; if(root->val > key){ ceil = root->val; root = root->right; } else root = root->right; } return ceil; }
Recording then going right is the wrong direction. A qualifying node means the answer is this node or something smaller, and smaller is to the left. Going right hunts for something larger, so the very first qualifying node is kept and the walk returns an answer that is too big — plausible, and wrong.
Ceil is the smallest value ≥ the key, and the key need not be in the tree at all. So the walk cannot just fall off the bottom and report failure: every time it stands on a node that would qualify, it records it and keeps going left, looking for something tighter. When the tree runs out, the answer is the last thing recorded. Watch the candidate panel rather than the node you are standing on — that is where the answer lives, and it is the same trick successor uses in unit 11.
“Smallest value greater than or equal to X” — X need not be present
Because the key may be absent, the walk can fall off the bottom with nothing to return. So every time you stand on a node that would qualify, record it and keep going left looking for something tighter. The last thing recorded is the answer.
int findCeil(Node* root, int key) { int ceil = -1; while (root) { if (root->val == key) return root->val; if (root->val > key) { ceil = root->val; root = root->left; } else root = root->right; } return ceil; }
def find_ceil(root, key): ceil = -1 while root: if root.val == key: return root.val if root.val > key: ceil = root.val; root = root.left else: root = root.right return ceil
Recording a candidate and then walking RIGHT keeps the first qualifier and returns a value that is too large. After recording, you always hunt in the direction of tighter answers.
The same walk with both the comparison and the direction reversed
IF FLOOR IS CEIL MIRRORED, WHY IS IT ITS OWN LECTURE?
val < key, RECORD, THEN GO RIGHTHow does the lecture define floor?
Greatest value ≤ the key — and the or equal to is load-bearing. If the key is present, the key is its own floor and its own ceil. Dropping equality gives you strict predecessor instead, which is a different problem and a different answer on exactly the inputs a judge tests.
You have working ceil code. What is the smallest correct edit that turns it into floor?
Both, or neither. Floor qualifies on val < key and then hunts larger, so it records and goes right. Flipping one of the two is the bug that makes this its own unit rather than a footnote: it returns a plausible number on many trees and the wrong one on the rest.
Floor is the largest value ≤ the key, and the code is ceil with the comparison and the direction both reversed: qualify on val < key, record, then go right looking for something larger. Flipping only one of the two is the bug that produces a plausible number on most inputs and the wrong one on the rest, which is why this gets its own unit rather than a footnote.
“Largest value less than or equal to X” — the mirror of ceil
Identical walk, with both the comparison and the direction reversed. Qualify on strictly smaller, record, then go right hunting something larger. Flipping only one of the two is the bug that makes this its own row rather than a footnote.
int findFloor(Node* root, int key) { int floor = -1; while (root) { if (root->val == key) return root->val; if (root->val < key) { floor = root->val; root = root->right; } else root = root->left; } return floor; }
def find_floor(root, key): floor = -1 while root: if root.val == key: return root.val if root.val < key: floor = root.val; root = root.right else: root = root.left return floor
Dropping the “or equal to” turns floor into strict predecessor. When the key IS in the tree the two answers differ, and that is exactly what a judge tests.
A failed search ends exactly where the new node belongs
WHY DOES INSERTING NEVER HAVE TO MOVE AN EXISTING NODE?
The lecture is emphatic that insertion must preserve one thing. What?
The BST property, over the subtrees. Note what is not preserved: the height. A plain BST does not rebalance on insert, so a run of increasing values grows a chain. Keeping the property is the requirement; keeping the height is what balanced trees add on top.
Why does insertion never have to move an existing node?
The failed search IS the insertion point. The walk only ever moved in directions the ordering permitted, so the null it stops at is the one place the value can sit without breaking anything. That is why insert is a search with one extra line, and why no subtree is ever rebuilt.
Recursive insert. One line makes the new node vanish. Which?
void insert(Node* root, int val){ if(root == nullptr){ root = new Node(val); return; } if(val < root->val) insert(root->left, val); else insert(root->right, val); }
The pointer is passed by value. root = new Node(val) rewrites a local copy of the pointer; the parent's left or right still holds null when the call returns. Nothing crashes and nothing is reported — the value is simply not in the tree. The fix is to return the node and assign it: root->left = insert(root->left, val).
Insert is not a separate algorithm. Run the search for the value you are inserting; because the value is not there, the walk ends at a null — and that null is precisely the slot where the value has to go, because the walk only ever went in directions the ordering permitted. So nothing existing moves, and no subtree is rebuilt. That is also why insertion order decides the shape: insert sorted data and every step goes the same way.
“Insert this value and keep it a BST”
Run the search for the value you are inserting. It is not there, so the walk ends at a null — and that null is the only slot the value can occupy, because the walk only ever moved in directions the ordering permitted. Nothing existing moves.
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; }
def insertIntoBST(root, val): if not root: return TreeNode(val) cur = root while True: if val < cur.val: if not cur.left: cur.left = TreeNode(val); break cur = cur.left else: if not cur.right: cur.right = TreeNode(val); break cur = cur.right return root
Passing the node pointer by value and assigning root = new Node(v) writes to a local copy. Nothing crashes; the value is simply not in the tree afterwards.
Three cases, and only the third is a real problem
WHAT REPLACES A NODE THAT HAS TWO CHILDREN?
Deleting a node with two children. Which value replaces it?
The in-order successor — or the predecessor, symmetrically. It is the only value larger than everything in the left subtree and smaller than everything else in the right, so it is the only value that fits the hole. Promoting a child breaks the order the moment that child has children of its own.
Why is the two-child case not actually the hardest thing here?
It reduces to a case you have already solved. The successor is the leftmost node of the right subtree, so by construction it has no left child — at most one child total. Copy its value up, then delete it, and that deletion is the easy case. The recursion bottoms out immediately.
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. Walking right lands on the largest value there, which is larger than other values in that same subtree — so promoting it puts a value above things that must exceed it. Walking s->left gives the successor. Predecessor works too, but then you must take the largest of the left subtree, not the right.
A leaf is unhooked. A node with one child is replaced by that child — both are one line. The only real case is two children, and the trick is that you do not move the node: you copy the in-order successor's value into it and then delete the successor instead. The successor is the smallest value in the right subtree, so it is the unique value that is larger than everything on the left and smaller than everything else on the right. And it has at most one child by construction — so the hard case reduces to an easy one.
“Remove this value and keep it a BST”
Two of the three cases are not really deletion. A leaf is unhooked; a node with one child is replaced by that child. The only real case is two children — and it is solved by not moving the node at all: copy the in-order successor's value in, then delete the successor.
Node* deleteNode(Node* root, int key) { if (!root) return nullptr; if (key < root->val) root->left = deleteNode(root->left, key); else if (key > root->val) root->right = deleteNode(root->right, key); else { if (!root->left) return root->right; if (!root->right) return root->left; Node* s = root->right; while (s->left) s = s->left; root->val = s->val; root->right = deleteNode(root->right, s->val); } return root; }
def deleteNode(root, key): if not root: return None if key < root.val: root.left = deleteNode(root.left, key) elif key > root.val: root.right = deleteNode(root.right, key) else: if not root.left: return root.right if not root.right: return root.left s = root.right while s.left: s = s.left root.val = s.val root.right = deleteNode(root.right, s.val) return root
Taking the largest of the RIGHT subtree instead of the smallest promotes a value above nodes that must exceed it. Successor is leftmost-of-right; predecessor is rightmost-of-LEFT.
In-order is sorted, so the kth node visited is the kth smallest
HOW DO YOU GET THE Kth SMALLEST WITHOUT SORTING ANYTHING?
The lecture opens with the naive solution before improving it. What is it?
Traverse into a container, sort, index. Naming it matters because of what it wastes: an in-order walk is already sorted, so the sort is pure loss and the container is O(n) memory for a question that needs a counter. The improvement is not a different algorithm, it is noticing what you already had.
Tree [8,4,12,2,6,10,14,1,3]. The 4th smallest is 4. How many of the 9 nodes does a counting in-order walk visit?
Four. In-order visits 1, 2, 3, 4 and stops — the remaining five nodes are never touched. That early exit is the entire optimisation, and it is what a sort-the-array solution throws away. Watch the bench: over half the tree stays untouched.
Counting in-order for the kth smallest. One line breaks the count. Which?
int kth(Node* n, int k){ int cnt = 0; if(!n) return -1; kth(n->left, k); if(++cnt == k) return n->val; return kth(n->right, k); }
The counter is per-call. Declaring cnt inside the function resets it in every subtree, so ++cnt is always 1 and the test only ever fires for k = 1. The counter has to outlive the recursion — pass it by reference, or make it a member. The discarded left result is a second real bug in this listing, which is why the shipped version returns through a reference parameter instead.
The whole problem is one observation: in-order traversal of a BST emits values in sorted order, so the k-th node visited is the k-th smallest. Nothing is sorted, nothing is collected into an array, and the traversal stops the moment the counter hits k — watch how many nodes are never visited at all. The counter has to be passed by reference; making it a local is the classic bug, and it silently restarts the count in every subtree.
“kth smallest” or “kth largest” in a BST
In-order emits sorted values, so the kth node visited is the kth smallest — no container, no sort, and the walk stops the moment the counter reaches k. For kth LARGEST, run the mirror: right, node, left.
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); }
def kthSmallest(root, k): st, cur = [], root while st or cur: while cur: st.append(cur); cur = cur.left cur = st.pop() k -= 1 if k == 0: return cur.val cur = cur.right
A counter declared inside the recursion resets in every subtree, so the test only fires for k = 1. It must be a reference parameter or a member.
Every node carries a window, and a parent alone cannot supply it
WHY DOES COMPARING EACH NODE TO ITS CHILDREN NOT WORK?
INT_MIN AS A BOUND REJECTS A TREE THAT CONTAINS ITWhy is comparing each node against its two children not a correct BST check?
The rule reaches further than one level. A 6 placed under 12 is a legal left child, and illegal as a descendant of 8, because everything in 8's right subtree must exceed 8. A parent-only check returns true on that tree. Carrying a window down is what catches it — this unit's bench is built on exactly that tree.
An alternative correct check is an in-order walk. What exactly must it verify?
Strictly increasing. In-order of a BST is sorted, so any value not greater than its predecessor proves a violation. Strictly matters: allowing equality accepts duplicates, which LeetCode 98 rejects. This is the same fact unit 07 counted on and unit 15 will hunt dips in.
Range-based validation. One line fails on a legitimate input. Which?
bool valid(Node* n, int lo, int hi){ if(!n) return true; if(n->val <= lo || n->val >= hi) return false; return valid(n->left, lo, n->val) && valid(n->right, n->val, hi); }
The sentinel collides with a real value. Called as valid(root, INT_MIN, INT_MAX), a node legitimately holding INT_MIN fails val <= lo and a valid tree is reported invalid. Use long bounds, or pass nullable pointers and skip the comparison when a bound is absent. LeetCode 98 tests this exact case.
This tree is drawn to break the wrong solution. Every node satisfies its own parent, so code that compares a node against node->left and node->right returns true — and the tree is not a BST. The 6 under 12 is fine as a left child and illegal as a descendant of 8, because everything in 8's right subtree must exceed 8. The fix is to carry a window down: each node narrows the range its subtrees may use. Use long for the bounds, or a tree containing INT_MIN breaks it.
“Is this a valid BST?” — the question the definition is really about
A node must satisfy every ancestor, not just its parent. So carry a window down: each node narrows the range its subtrees may use. The alternative is an in-order walk that must strictly increase, which is the same fact from the other side.
bool valid(Node* n, long lo, long hi) { if (!n) return true; if (n->val <= lo || n->val >= hi) return false; return valid(n->left, lo, n->val) && valid(n->right, n->val, hi); } bool isValidBST(Node* root) { return valid(root, LONG_MIN, LONG_MAX); }
def isValidBST(root): def ok(n, lo, hi): if not n: return True if not (lo < n.val < hi): return False return ok(n.left, lo, n.val) and ok(n.right, n.val, hi) return ok(root, float('-inf'), float('inf'))
INT_MIN and INT_MAX as starting bounds reject a valid tree that contains those values. Use long, or nullable bounds.
The first node where the two targets disagree
WHY DOES LCA IN A BST NEED NO RECURSION AT ALL?
The lecture defines LCA by drawing both root-paths. What is the LCA on that picture?
The first intersection of the two paths. That framing is what makes the BST shortcut obvious: the paths run together while both targets lie on the same side, and split at the first node where they disagree. So the split point is the intersection, and you can stop there.
In a general binary tree, LCA recurses into both subtrees and returns results upward. Why is none of that needed here?
The ordering answers what the search was for. In a general tree you must look in both subtrees because nothing tells you where a value is. Here one comparison does, so it is a single walk down with no return path and no bookkeeping — O(h) time and O(1) space iteratively.
Tree [8,4,12,2,6,10,14,1,3,5,7]. LCA of 1 and 7?
4. At 8 both 1 and 7 are smaller, so both go left. At 4, 1 is smaller and 7 is larger — they disagree, and 4 is the answer. Note it is not the root: the root is the first place they could split, not the first place they do.
In a general binary tree, LCA means recursing into both subtrees and returning results back up. In a BST it is a single walk with no recursion at all: while both targets are smaller than the node, go left; while both are larger, go right. The first node where they disagree — one goes left, one goes right, or one IS the node — has both beneath it and nothing lower does. You stop the instant it happens.
“Lowest common ancestor” — and the tree is a BST
Walk from the root while both targets lie on the same side. The first node where they disagree — one goes left, one goes right, or one IS the node — has both beneath it, and nothing lower does. You stop the instant it happens.
Node* lowestCommonAncestor(Node* root, Node* p, Node* q) {
while (root) {
if (p->val < root->val && q->val < root->val) root = root->left;
else if (p->val > root->val && q->val > root->val) root = root->right;
else return root;
}
return nullptr;
}def lowestCommonAncestor(root, p, q): while root: if p.val < root.val and q.val < root.val: root = root.left elif p.val > root.val and q.val > root.val: root = root.right else: return root return None
The LCA is not the root just because the targets are far apart, and it is not necessarily either target's parent. It is the first split, wherever that falls.
The bound is the information the array does not give you
PREORDER ALONE IS AMBIGUOUS FOR A BINARY TREE — WHY NOT FOR A BST?
Before the one-pass method, the lecture names the naive construction. What is it?
Insert each value from the root in turn. That is O(n²) in the worst case — and the worst case is a sorted preorder, which is a chain. Worth naming because it is correct and will pass small tests, so the reason to replace it is the bound, not the behaviour.
Preorder alone determines a binary search tree but not a general binary tree. What supplies the missing information?
The ordering. For a general tree you need two traversals because preorder cannot say where the left subtree ends. In a BST it can: the left subtree is exactly the prefix of values below the node, and the first value above it starts the right subtree. That boundary is what the upper bound detects in one pass.
Preorder [8,5,1,7,10,12], building 8's left subtree with bound 8. The scan reaches 10. What happens?
It returns, leaving 10 unconsumed. That is the whole mechanism: the recursion does not look for the subtree boundary, it walks into it and is turned back by the bound. Because the index is shared and 10 was never consumed, the caller's right branch picks it up next. Skipping it would lose a node.
A preorder list alone is ambiguous for a general binary tree, and unambiguous for a BST — the ordering supplies the missing structure. The naive build is O(n²) (insert each value from the root) and the sort-and-recurse trick is O(n log n). This is one pass: each call carries an upper bound, takes the next value only if it is under that bound, and returns the moment it is not. That return is what tells the scan where a subtree ends, which is the only thing the array does not say out loud.
“Build the BST whose preorder is this array”
Preorder alone is ambiguous for a general binary tree and unambiguous for a BST, because the ordering supplies the missing structure. One pass: each call carries an upper bound and returns the moment the next value exceeds it — and that return is what marks where a subtree ends.
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 = 0 def build(bound): nonlocal i if i == len(pre) or pre[i] > bound: return None n = TreeNode(pre[i]); i += 1 n.left = build(n.val) n.right = build(bound) return n return build(float('inf'))
Advancing the index past a rejected value loses a node. The index must only move when a value is actually taken.
The candidate trick again, on the in-order order
WHERE IS THE SUCCESSOR OF A NODE WITH NO RIGHT CHILD?
The lecture defines the successor through one traversal in particular. Which, and in what order?
In-order: left, node, right. The successor is defined as the next value in that sequence, and since in-order of a BST is sorted, the successor is just the next larger value. Naming the traversal is what turns a tree question into a sorted-list question.
A node has no right child. Where is its successor?
The last left turn on the way down. With no right child the answer is not below the node at all — it is above it. Rather than special-casing the two shapes, walk from the root once and record a candidate whenever you turn left; that candidate is the answer. It is the ceil trick from unit 03, and it needs no parent pointers.
Successor by carried candidate. One line is wrong. Which?
Node* successor(Node* root, int key){ Node* best = nullptr; while(root){ if(root->val >= key){ best = root; root = root->left; } else root = root->right; } return best; }
>= lets the key be its own successor. With the key present in the tree, the walk records the key itself and returns it — so successor(8) comes back as 8. Successor is strictly greater; ceil is the one that allows equality. One character, and it only shows up when the key is actually in the tree.
The successor of a node with a right child is easy — the leftmost node of that subtree. The case that catches people is a node with no right child, where the answer is not below it at all: it is the deepest ancestor the walk turned left at. Rather than special-casing the two shapes, this walks from the root once and records a candidate whenever it turns left. Same shape as ceil, and it needs no parent pointers.
“The next value after this one, in sorted order”
With a right child the answer is the leftmost node of that subtree. Without one it is not below the node at all — it is the deepest ancestor the walk turned left at. Rather than special-case the shapes, walk from the root once and record a candidate on every left turn.
Node* successor(Node* root, Node* p) {
Node* best = nullptr;
while (root) {
if (root->val > p->val) { best = root; root = root->left; }
else root = root->right;
}
return best;
}def inorderSuccessor(root, p): best = None while root: if root.val > p.val: best = root; root = root.left else: root = root.right return best
Using >= lets a present key be its own successor. Successor is STRICTLY greater; ceil is the one that allows equality.
An in-order traversal you can pause, in O(h) space
HOW DO YOU HAND BACK ONE SORTED VALUE AT A TIME WITHOUT FLATTENING?
next() AND hasNext() — IT MUST PAUSEnext() IS AMORTISED O(1)The lecture names the two operations the iterator has to support. Which?
next() and hasNext(). That interface is what forces the design: the traversal has to be pausable, giving one value and then stopping until asked again. A plain recursive in-order cannot pause, which is why the recursion has to be turned into an explicit stack.
Flattening the tree into a sorted vector in the constructor also satisfies the interface. Why is it rejected?
Space. Flattening is correct and easy and costs O(n) — which is the entire difficulty of the problem thrown away. The stack holds only the left spine of what remains, so it never exceeds the height. On a balanced tree with 10⁵ nodes that is 17 pointers rather than 100000.
Each node is pushed once and popped once across a full traversal. What does that make next()?
Amortised O(1), and the distinction is the point. A single next() can push a long left spine and cost O(h). But across the whole traversal each node is pushed and popped exactly once, so n calls cost O(n) total. Claiming worst-case O(1) in an interview is the wrong answer to a question they are asking on purpose.
Flattening the tree into a sorted array makes next() trivial and costs O(n) memory, which is the whole difficulty of the problem thrown away. The iterator instead keeps a stack holding only the left spine of what remains: the constructor pushes root, root->left, root->left->left … and next() pops one and pushes the left spine of its right child. The stack never exceeds the height. Each node is pushed once and popped once across the whole traversal, so next() is amortised O(1) — individual calls are not.
Two BSTs are two sorted sequences, and you already know how to merge those
CAN YOU MERGE TWO BSTs WITHOUT BUILDING A THIRD TREE?
This row has no lecture in the playlist. Given in-order is sorted, what does merging two BSTs reduce to?
The merge step of merge sort. Once in-order-is-sorted has landed, this stops being a tree problem: two BSTs are two sorted sequences. Inserting one tree into the other is O(n log m) at best and O(n·m) on a chain, and it rebuilds structure you were handed.
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 — you must touch every value. The iterators from unit 12 hold only two left spines, so the memory is the two heights rather than the two trees. It is also why unit 12 is in this deck despite having no sheet row of its own.
Once in-order-is-sorted has landed, this problem stops being about trees. Two BSTs are two sorted sequences; merging them is the merge step of merge sort. The lazy version collects both in-orders into arrays and merges — O(n+m) time and O(n+m) space. Driving two iterators from unit 12 instead keeps the time and drops the space to O(h1+h2), and on balanced trees that is the difference between a hundred thousand and thirty-four.
“All elements of two BSTs, in sorted order”
Once in-order-is-sorted has landed, this stops being a tree problem. Two BSTs are two sorted sequences, and merging two sorted sequences is the merge step of merge sort. Driving two iterators instead of two arrays keeps the time and drops the space to the two heights.
vector<int> getAllElements(Node* a, Node* b) { vector<int> out; stack<Node*> s1, s2; auto push = [](stack<Node*>& s, Node* n) { while (n) { s.push(n); n = n->left; } }; push(s1, a); push(s2, b); while (!s1.empty() || !s2.empty()) { stack<Node*>& s = s2.empty() || (!s1.empty() && s1.top()->val <= s2.top()->val) ? s1 : s2; Node* n = s.top(); s.pop(); out.push_back(n->val); push(s, n->right); } 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
Inserting one tree's nodes into the other is O(n log m) at best and O(n·m) on a chain — and it rebuilds structure you were already handed.
Two pointers, where the array is a tree
WHY IS A HASH SET THE WRONG ANSWER TO A PROBLEM ABOUT A BST?
The lecture is emphatic about one constraint on the pair. Which?
Two distinct elements. It is why the two-pointer condition is a < b and not a != b: the pointers must never meet or cross, or a value pairs with itself and k = 2·v is reported as a hit. On LeetCode 653 that is exactly the failing case.
The lecture names a prerequisite problem. Which?
Two Sum. The point of naming it is that this problem is not new — it is Two Sum on a sorted input, and the tree is only the container the sorted input arrives in. Recognising an old problem in unfamiliar clothing is the skill an OA actually measures.
A hash set also solves this in O(n) time. What does the two-iterator version do better?
Space, by using what you were given. The set is correct and accepted, and it discards the one property the input handed you for free: the values are already in order. Two iterators are the two ends of a sorted array — O(n) time, O(h) space.
The hash-set answer works, is accepted, and costs O(n) extra space — and it throws away the one thing the input handed you for free, which is that the values are already in order. Run a forward iterator and a reverse iterator as the two ends of a sorted array: sum too small, advance the low end; too large, retreat the high end. O(n) time, O(h) space. The condition is a < b, not a != b — the pointers must never cross or pass each other and pair a value with itself.
“Do two distinct nodes sum to k?”
This is Two Sum, and the tree is only the container the sorted input arrives in. A forward iterator and a reverse iterator are the two ends of a sorted array: sum too small, advance the low end; too large, retreat the high end.
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) return true; if (a + b < k) a = lo.next(); else b = hi.next(); } return false; }
def findTarget(root, k): vals = [] def ino(n): if not n: return ino(n.left); vals.append(n.val); ino(n.right) ino(root) i, j = 0, len(vals) - 1 while i < j: s = vals[i] + vals[j] if s == k: return True if s < k: i += 1 else: j -= 1 return False
The loop condition must be a < b. Using a != b lets the pointers cross, and a value pairs with itself so k = 2v is reported as a hit.
A sorted sequence with two elements swapped falls in at most two places
HOW MANY PLACES CAN A TWO-NODE SWAP SHOW UP IN AN IN-ORDER WALK?
What does the problem guarantee about the damage to the tree?
Exactly two, swapped. That guarantee is what makes an O(n) scan sufficient: a sorted sequence with two elements exchanged has at most two places where it falls. Without it you would have to rebuild the tree rather than repair it.
In-order of the damaged tree reads 12 4 6 8 10 2 14. Which two values must be swapped back?
12 and 2. There are two dips: 12 → 4 and 10 → 2. With two dips the culprits are the first value of the first dip and the second value of the last — 12 and 2. Taking both values from the same dip is the standard error and gives 12 and 4, which is option two for exactly that reason.
Your code handles two dips correctly and fails a small test. What shape did you miss?
Adjacent nodes give only ONE dip. Swap two neighbours in a sorted sequence and there is a single fall, from which both culprits come. Code that assumes two dips leaves the second pointer null and crashes or does nothing. It is the smallest test anyone writes, which is why this bug is caught immediately and still written constantly.
Walk in-order and the values should only ever rise. Two nodes swapped produce at most two places where they fall. If the swapped pair is far apart you see two dips, and the culprits are the first value of the first dip and the second value of the last. If the pair is adjacent you see only one dip, and both culprits come from it. Handling only the two-dip case is the standard bug, and it fails on precisely the smallest test case anyone tries.
“Exactly two nodes were swapped — put them back”
In-order should only ever rise. Two swapped nodes produce at most two places where it falls. Far apart gives two dips and the culprits are the first value of the first and the second value of the last; adjacent gives one dip and both culprits come from it.
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 = None def ino(n): nonlocal first, second, prev if not n: return ino(n.left) if prev and n.val < prev.val: if not first: first, second = prev, n else: second = n prev = n ino(n.right) ino(root) first.val, second.val = second.val, first.val
Handling only the two-dip case leaves the second pointer null when the swapped pair is adjacent, which is the smallest test anyone writes.
A parent cannot judge itself until both children have reported
WHY MUST THIS BE POST-ORDER, AND WHAT HAS TO TRAVEL UPWARD?
The lecture opens by showing why the whole tree is not a BST. What is its example?
A 7 sitting in the right subtree of 10. It is the unit 08 violation again: legal against its immediate parent, illegal against an ancestor. That is why the recursion must return the subtree's min and max upward — a parent cannot see the values that break it otherwise.
Why must this be post-order rather than pre-order?
The information flows upward. To decide whether it roots a BST, a node needs the left subtree's max, the right subtree's min, and both verdicts — all facts about its children. Pre-order carries information down, which is the wrong direction, and would force a re-scan per node: O(n²) instead of O(n).
Tree [10,5,15,1,8,null,7]. What is the largest BST subtree, and how big?
The subtree rooted at 5 — nodes 5, 1 and 8 — size 3. The whole tree fails on 7, which sits right of 10 and does not exceed it. Note what that costs 15: perfectly ordered in itself, ruined by one child, and reduced to a best of 1. A node can be locally fine and still contribute nothing.
Checking each subtree independently with a validator is O(n²). One post-order pass is O(n), and it works because each call returns four facts rather than one: the subtree's min, max, size and verdict. A node is the root of a BST exactly when both children are, and its own value fits strictly between the left's max and the right's min. Watch node 15 here — perfectly ordered in itself, ruined by one child, and reduced to a best of 1.
“Largest subtree that is a BST” — inside a tree that is not one
A node cannot judge itself. It needs the left subtree's maximum, the right subtree's minimum and both verdicts — all facts about its children — so the information travels upward and the traversal must be post-order. Each call returns four things instead of one.
struct Info { int mn, mx, size; bool ok; }; Info go(Node* n, int& best) { if (!n) return { INT_MAX, INT_MIN, 0, true }; 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 { INT_MIN, INT_MAX, max(l.size, r.size), false }; }
def largestBSTSubtree(root): best = 0 def go(n): nonlocal best if not 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 (float('-inf'), float('inf'), max(lsz, rsz), False) go(root) return best
Returning only a boolean is not enough — the parent cannot check its own value without the children's min and max, and re-computing those is what makes the naive version quadratic.
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 walk cannot just return where it stops — the answer is the last node that could still have been it. Ceil, floor and successor are all this one shape, which is why they are three units and one idea.
Which of these genuinely requires post-order rather than any other traversal?
Largest BST subtree. A node cannot decide whether it roots a BST until both children report their min, max, size and verdict — the information travels upward, which is what post-order is. Kth is in-order, LCA is a walk down, and validation can be done either by a downward window or an in-order scan.
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. The vector and the hash set are both O(n) and both discard the fact that the input is already ordered. The iterators are the two ends of a sorted array without ever materialising the array, which is the whole reason unit 12 is in this deck.
Deleting a node with two children, you copy the in-order successor's value up. What must happen next?
Delete the successor. Copying the value leaves that value in the tree twice, so the original has to go — and because the successor is the leftmost node of the right subtree, it has no left child and falls into the easy case. That reduction is why the hard case is not actually hard.
You must return values in sorted order but the caller may stop at any point. Which design?
The controlled stack. Flattening costs O(n) memory and throws the problem away; re-running the traversal costs O(n) per value. The stack holds only the left spine of what remains — O(h) — and each node is pushed and popped once, so next() is amortised O(1).
Which single fact does the biggest share of this deck rest on?
In-order is sorted. Kth smallest, validate, recover, merge, two-sum and the iterator are all that one fact used differently — six of the sixteen rows, and the hardest four among them. The others are true and local; this one is the bridge from “tree” to “sorted sequence”, and it is what the rest is built on.
Not one of these crashes. Every one returns something that looks like an answer — a validator that accepts an invalid tree, a minimum that is not the minimum, a counter that only ever reaches one. That is what makes them expensive.
node->left->val < node->val at every node returns TRUE on trees that are not BSTs. A 6 under a 12 in the right subtree of an 8 satisfies its parent and breaks its grandparent. Carry a window down instead — and unit 08's bench is that exact tree.
valid(root, INT_MIN, INT_MAX) looks airtight and rejects a valid tree containing INT_MIN, because the node fails val <= lo against its own value. Use long, or pass nullable bounds and skip the comparison when one is absent.
The leftmost node cannot have a left child; it can perfectly well have a right one. Code that loops while(n->left && n->right) or tests isLeaf stops early and returns a value that is not the minimum, silently, on exactly that shape.
In ceil, a qualifying node means the answer is this or something SMALLER, so you go left. Going right keeps the first qualifier and returns a value that is too large. Floor is the mirror, and flipping only one of the comparison and the direction is the way this gets written wrong.
A local counter resets in every subtree, so ++cnt == k only ever fires for k = 1. It has to outlive the recursion — a reference parameter or a member. The answer that comes back is a real node's value, which is what makes it hard to see.
Two swapped nodes give two dips when they are far apart and ONE when they are adjacent. Code written for the two-dip case leaves the second pointer null on the adjacent case — and adjacent is the smallest test anybody writes.
Every operation in this step with its cost and the one line that selects it. This is the night-before page.
A binary search tree is a binary tree with one promise held at every node, and every problem in this step is that promise cashed in. Six of them are a walk down, where one comparison names a direction and the other subtree is never seen. The other nine are the same observation twice removed: in-order emits sorted values, so counting, validating, repairing, merging and pairing are all questions about a sorted list that never gets built. Next is step 15, graphs, where nothing is ordered and the walk has to remember where it has been.
Step 14, all 16 sheet rows, 15 lectures (L39–L53). Unit 12 is a lecture with no sheet row; unit 13 is a sheet row with no lecture. Every bench fills in values the build re-derived and asserted, and every drill that quotes a lecture is checked verbatim against its transcript — except in units 3, 6, 8 and 13, where no usable transcript exists and the drills cite the moment instead.
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.