INVARIANT · BST · Binary Search Trees
01
00/18
01 / COVER 14 · BST
INVARIANT · 14 · BINARY SEARCH TREES
BINARY SEARCH TREES

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  navigate SPACE next   DOUBLE-CLICK to advance I index   G goto problem   P predict H hide solutions   F fullscreen
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
02 / START HERE READ 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 / Space 2×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 progress GJump straight to a problem by its number FFullscreen

While you study

HHide solutions — blurs code and steps so you try first PPredict 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 / SIGNALS WHEN 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 / CONSTRAINTS BEFORE 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 / ROADMAP WHAT 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 / INDEX PRESS 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
SOLVED HAS A JUDGE LINK CONCEPT — DRILLS ONLY
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
07 / INTRO UNIT 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 / MECHANISM UNIT 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 / DRILL UNIT 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 / DRILL UNIT 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

EASY concept CONCEPT · 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
  1. Left subtree: EVERY value is smaller than the node
  2. Right subtree: EVERY value is larger than the node
  3. No equality — a duplicate has no legal side unless the problem names one
  4. Both subtrees are themselves BSTs, all the way down
  5. 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.
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 / WARMUP AFTER 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 / WARMUP AFTER 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?

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 uses the order. It finds the key, but visits every node: O(n).

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
14 / INTRO UNIT 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 / MECHANISM UNIT 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 / MECHANISM UNIT 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 / DRILL UNIT 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 / DRILL UNIT 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?

int findMin(Node* root){
    while(root->left && root->right)
        root = root->left;
    return root->val;
}

Test the left child alone, not with &&. The minimum may have a right child.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
19 / PROBLEM #02 · WALK · EASY

Search in a Binary Search Tree

EASY walk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Find the node with this value” — and the tree is a BST

INTUITION

Each comparison picks a direction and drops the other subtree whole. No recursion needed.

STEPS
  1. While the node exists and does not hold the key
  2. Key smaller: move to the left child
  3. Key larger: move to the right child
  4. Return the node — it is null exactly when the key was absent
BRUTEO(n) as a binary tree
→
OPTIMALO(h)
↕ SCROLL
Node* searchBST(Node* root, int val) {
    while (root && root->val != val)
        root = val < root->val ? root->left : root->right;
    return root;
}
TIMEO(h)one comparison per level
SPACEO(1)iterative, so no stack
TRAP

Searching both subtrees. Correct, but O(n): it throws away the ordering.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
20 / PROBLEM #03 · WALK · EASY

Find Min/Max in BST

EASY walk ▶ SOLVE ON GEEKSFORGEEKS
SIGNAL — WHAT GIVES IT AWAY

“Smallest” or “largest” value in a BST, with no key given

INTUITION

No comparison needed: go left until there is no left. That is the minimum.

STEPS
  1. Minimum: follow left children until one is null
  2. Maximum: follow right children until one is null
  3. Return that node's value
  4. Neither ever compares against a target
BRUTEO(n) scanning every node
→
OPTIMALO(h)
↕ SCROLL
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;
}
TIMEO(h)one edge per level
SPACEO(1)iterative
TRAP

The minimum is NOT always a leaf. It has no left child, but may have a right one.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
21 / INTRO UNIT 03 · CEIL — CARRY A CANDIDATE

UNIT 03 — CEIL — CARRY A CANDIDATE

The answer may be a node the walk already passed

THE QUESTION THIS UNIT ANSWERS

WHAT DO YOU RETURN WHEN THE KEY IS NOT IN THE TREE AT ALL?

ceilcandidateabsent key
WHAT TO LOOK FOR
  • 01CEIL IS THE SMALLEST VALUE ≥ THE KEY, AND THE KEY MAY BE ABSENT
  • 02A QUALIFYING NODE IS RECORDED, NOT RETURNED
  • 03AFTER RECORDING, GO LEFT — YOU WANT SOMETHING TIGHTER
  • 04WHEN THE WALK RUNS OUT, THE ANSWER IS THE LAST THING RECORDED
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
22 / MECHANISM UNIT 03 · BSTCEIL · CODE MIRRORED

THE ANSWER MAY BE A NODE YOU ALREADY WALKED PAST

Ceil is the smallest value ≥ the key, which may be absent. On each node that qualifies, record it and go left. The last record is the answer.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
23 / DRILL UNIT 03 · CEIL — CARRY A CANDIDATE · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

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. So the walk can fall off the bottom with nothing to return.

DRILL 02 · TRACE

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, answer 10. 8 is too small; 12 qualifies and is recorded; 10 qualifies and replaces it.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
24 / DRILL UNIT 03 · CEIL — CARRY A CANDIDATE · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · BUG

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;
}

Going right after recording is wrong. A qualifying node means the answer is this or smaller, and smaller is left.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
25 / PROBLEM #04 · CANDIDATE · EASY

Floor and Ceil in a BST

EASY candidate ▶ SOLVE ON GEEKSFORGEEKS
SIGNAL — WHAT GIVES IT AWAY

“Smallest value greater than or equal to X” — X need not be present

INTUITION

The key may be absent. On every node that qualifies, record it and go left for something tighter. The last record is the answer.

STEPS
  1. ceil = -1 to start: what this judge wants when nothing qualifies, and safe only because its values are positive
  2. At each node: if it equals the key, that IS the ceil
  3. If it is larger, record it as the candidate and go LEFT
  4. If it is smaller, it cannot qualify — go RIGHT
  5. When the walk runs out, return the candidate
BRUTEO(n) collecting and scanning
→
OPTIMALO(h)
↕ SCROLL
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;
}
TIMEO(h)one comparison per level
SPACEO(1)one integer of state
TRAP

Recording, then walking right. That keeps the first qualifier, which is too large.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
26 / INTRO UNIT 04 · FLOOR — THE MIRROR

UNIT 04 — FLOOR — THE MIRROR

The same walk with both the comparison and the direction reversed

THE QUESTION THIS UNIT ANSWERS

IF FLOOR IS CEIL MIRRORED, WHY DOES IT GET ITS OWN UNIT?

floormirrorpredecessor
WHAT TO LOOK FOR
  • 01FLOOR IS THE GREATEST VALUE ≤ THE KEY
  • 02THE OR EQUAL TO IS LOAD-BEARING — A PRESENT KEY IS ITS OWN FLOOR
  • 03EQUAL: RETURN IT · SMALLER: RECORD IT AND GO RIGHT
  • 04FLIPPING ONLY ONE OF THE TWO IS THE BUG THIS UNIT EXISTS FOR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
27 / MECHANISM UNIT 04 · BSTFLOOR · CODE MIRRORED

THE SAME WALK WITH BOTH SIGNS FLIPPED

Ceil mirrored: qualify on val < key, record, go right. Flip both the comparison and the direction.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
28 / DRILL UNIT 04 · FLOOR — THE MIRROR

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

What is the floor of a key?

Greatest value ≤ the key. If the key is present, it is its own floor.

DRILL 02 · TRANSFER

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.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
29 / PROBLEM #05 · CANDIDATE · EASY

Floor in a Binary Search Tree

EASY candidate ▶ SOLVE ON GEEKSFORGEEKS
SIGNAL — WHAT GIVES IT AWAY

“Largest value less than or equal to X” — the mirror of ceil

INTUITION

Ceil, mirrored. Equal: return it. Smaller: record and go right. Larger: go left.

STEPS
  1. floor = -1 to start: what this judge wants when nothing qualifies, and safe only because its values are positive
  2. If the node equals the key, that IS the floor
  3. If it is smaller, record it and go RIGHT
  4. If it is larger, it cannot qualify — go LEFT
  5. Return the last candidate recorded
BRUTEO(n) collecting and scanning
→
OPTIMALO(h)
↕ SCROLL
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;
}
TIMEO(h)one comparison per level
SPACEO(1)one integer of state
TRAP

Dropping the “or equal”. When the key is present, it is its own floor.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
30 / INTRO UNIT 05 · INSERT WITHOUT RESTRUCTURING

UNIT 05 — INSERT WITHOUT RESTRUCTURING

A failed search ends exactly where the new node belongs

THE QUESTION THIS UNIT ANSWERS

WHY DOES INSERTING NEVER HAVE TO MOVE AN EXISTING NODE?

insertnull slotshape
WHAT TO LOOK FOR
  • 01THE WALK IS THE SEARCH FOR THE VALUE YOU ARE INSERTING
  • 02THE NULL IT ENDS ON IS THE ONLY LEGAL SLOT
  • 03NOTHING EXISTING MOVES, AND NO SUBTREE IS REBUILT
  • 04THE HEIGHT IS NOT PRESERVED — SORTED INPUT BUILDS A CHAIN
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
31 / MECHANISM UNIT 05 · BSTINSERT · CODE MIRRORED

A FAILED SEARCH ENDS EXACTLY WHERE THE NODE BELONGS

Search for the value. The walk ends at a null, and that is its slot. Nothing existing moves.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
32 / DRILL UNIT 05 · INSERT WITHOUT RESTRUCTURING · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Insertion must preserve one thing. What?

The BST property, over the subtrees. Note what is not preserved: the height.

DRILL 02 · TRANSFER

Why does insertion never have to move an existing node?

The failed search IS the insertion point. The null it stops at is the only place the value fits.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
33 / DRILL UNIT 05 · INSERT WITHOUT RESTRUCTURING · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · BUG

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) changes a local copy; the parent still holds null.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
34 / PROBLEM #06 · RESTRUCTURE · MED

Insert a given node in BST

MED restructure ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Insert this value and keep it a BST”

INTUITION

Search for the value. It ends at a null, and that null is where the value goes. Nothing else moves.

STEPS
  1. The value is promised not to be in the tree, so the equal case never happens
  2. If the tree is empty, the new node is the root
  3. Walk down comparing, exactly as a search would
  4. When the child on the chosen side is null, attach there
  5. 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;
}
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 / INTRO UNIT 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 / MECHANISM UNIT 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 / DRILL UNIT 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 / DRILL UNIT 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
39 / PROBLEM #07 · RESTRUCTURE · MED

Delete a node in BST

MED restructure ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Remove this value and keep it a BST”

INTUITION

Leaf: unhook it. One child: the child moves up. Two children: copy in the successor's value, then delete the successor.

STEPS
  1. Walk down to find the node, recursing into the correct side
  2. No left child: return the right child (covers leaf too)
  3. No right child: return the left child
  4. Two children: find the leftmost node of the right subtree
  5. Copy its value up, then delete that value from the right subtree
BRUTEO(n) rebuilding from the values
→
OPTIMALO(h)
↕ SCROLL
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;   // (a real program would also free root)
        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;
}
TIMEO(h)one walk down, then one more
SPACEO(h)the recursion stack
TRAP

Taking the largest of the RIGHT subtree. The successor is the leftmost of the right subtree.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
40 / INTRO UNIT 07 · INORDER IS SORTED

UNIT 07 — INORDER IS SORTED

In-order is sorted, so the kth node visited is the kth smallest

THE QUESTION THIS UNIT ANSWERS

HOW DO YOU GET THE Kth SMALLEST WITHOUT SORTING ANYTHING?

kth smallestcounterearly exit
WHAT TO LOOK FOR
  • 01THE NAIVE FORM COLLECTS EVERYTHING AND SORTS AN ALREADY-SORTED WALK
  • 02IN-ORDER + A COUNTER NEEDS NO CONTAINER AT ALL
  • 03THE TRAVERSAL STOPS THE MOMENT THE COUNTER REACHES k
  • 04THE COUNTER MUST BE BY REFERENCE, OR IT RESETS PER SUBTREE
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
41 / MECHANISM UNIT 07 · BSTKTH · CODE MIRRORED

STOP THE WALK, DO NOT SORT THE TREE

In-order is sorted, so the k-th node visited is the k-th smallest. Stop at k. Pass the counter by reference.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
42 / DRILL UNIT 07 · INORDER IS SORTED · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Which first attempt at kth smallest ignores the ordering and pays for a sort it does not need?

Traverse into a list, sort, index. In-order is already sorted, so the sort and the list are wasted.

DRILL 02 · TRACE

Tree [8,4,12,2,6,10,14,1,3]. The 4th smallest is 4. How many nodes does a counting in-order walk count before it stops?

Four. The walk goes down 8, 4, 2, 1, then counts 1, 2, 3, 4 and stops.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
43 / DRILL UNIT 07 · INORDER IS SORTED · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · BUG

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;
    int left = kth(n->left, k);
    if(left != -1) return left;
    if(++cnt == k) return n->val;
    return kth(n->right, k);
}

The counter is per call. Declared inside, it resets in every subtree, so it only fires for k = 1.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
44 / PROBLEM #08 · INORDER · MED

Kth Smallest and Largest element in BST

MED inorder ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“kth smallest” or “kth largest” in a BST

INTUITION

In-order is sorted, so the kth node visited is the kth smallest. Stop as soon as the counter reaches k.

STEPS
  1. Walk in-order: left subtree, node, right subtree
  2. Increment a counter as each node is visited
  3. When the counter equals k, that node is the answer
  4. Stop — the nodes after it are never counted
  5. 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;
}
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 / INTRO UNIT 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
46 / MECHANISM UNIT 08 · BSTVALIDATE · CODE MIRRORED

THE TREE THAT PASSES A PARENT-ONLY CHECK

Every node here fits its parent, yet it is not a BST: the 6 sits in 8's right subtree. Carry a window down instead.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
47 / DRILL UNIT 08 · VALIDATE BY RANGE · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Why is comparing each node against its two children not a correct BST check?

The rule reaches past one level. A 6 under 12 is a fine left child, but it is in 8's right subtree and smaller than 8.

DRILL 02 · TRANSFER

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.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
48 / DRILL UNIT 08 · VALIDATE BY RANGE · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · BUG

Range-based validation. One line fails on a legitimate input. Which?

// called as valid(root, INT_MIN, INT_MAX)
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 start bound collides with a real value. A node holding INT_MIN fails val <= lo, so a valid tree is rejected.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
49 / PROBLEM #09 · INORDER · MED

Check if a tree is a BST or not

MED inorder ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Is this a valid BST?” — the question the definition is really about

INTUITION

A node must fit every ancestor, not just its parent. Carry a window down; each node narrows it for its subtrees.

STEPS
  1. Start at the root with an unbounded window
  2. A node must lie strictly inside its window, or the tree fails
  3. Recurse left with the upper bound tightened to this node's value
  4. Recurse right with the lower bound raised to this node's value
  5. Both sides must pass
BRUTEO(n²) re-scanning subtrees
→
OPTIMALO(n)
↕ SCROLL
bool valid(Node* n, long long lo, long 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, LLONG_MIN, LLONG_MAX);
}
TIMEO(n)each node visited once
SPACEO(h)the recursion stack
TRAP

INT_MIN and INT_MAX as starting bounds reject a valid tree that contains those values. Use long long bounds.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
50 / INTRO UNIT 09 · LCA IS THE SPLIT POINT

UNIT 09 — LCA IS THE SPLIT POINT

The first node where the two targets disagree

THE QUESTION THIS UNIT ANSWERS

WHY DOES LCA IN A BST NEED NO RECURSION AT ALL?

LCAsplit pointroot path
WHAT TO LOOK FOR
  • 01BOTH SMALLER, GO LEFT · BOTH LARGER, GO RIGHT
  • 02THE FIRST DISAGREEMENT IS THE ANSWER, AND YOU STOP THERE
  • 03A GENERAL TREE MUST SEARCH BOTH SUBTREES AND RETURN UPWARD
  • 04IT IS THE LAST NODE THE TWO ROOT-PATHS SHARE
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
51 / MECHANISM UNIT 09 · BSTLCA · CODE MIRRORED

THE FIRST DISAGREEMENT IS THE ANSWER

One walk, no recursion: both smaller, go left; both larger, go right. The first node where they split is the LCA.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
52 / DRILL UNIT 09 · LCA IS THE SPLIT POINT · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Draw the path from the root to each target. Where on that picture is the LCA?

The last shared node. Both paths start at the root and run together while both targets lie on the same side.

DRILL 02 · TRANSFER

In a general binary tree, LCA recurses into both subtrees and returns results upward. Why is none of that needed here?

The ordering says where to look. A general tree gives no hint, so you search both sides.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
53 / DRILL UNIT 09 · LCA IS THE SPLIT POINT · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

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 go left. At 4 they split.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
54 / PROBLEM #10 · WALK · MED

LCA in BST

MED walk ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Lowest common ancestor” — and the tree is a BST

INTUITION

Walk from the root while both targets are on the same side. The first node where they split is the LCA.

STEPS
  1. Both targets smaller than the node: go left
  2. Both targets larger: go right
  3. Otherwise they have split, and this node is the LCA
  4. No recursion and no returning results upward
BRUTEO(n) as a general binary tree
→
OPTIMALO(h)
↕ SCROLL
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;
}
TIMEO(h)one comparison per level
SPACEO(1)iterative
TRAP

Assuming it is the root or a parent. It is the first node where the two targets split.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
55 / INTRO UNIT 10 · BUILD FROM PREORDER

UNIT 10 — BUILD FROM PREORDER

The bound is the information the array does not give you

THE QUESTION THIS UNIT ANSWERS

PREORDER ALONE IS AMBIGUOUS FOR A BINARY TREE — WHY NOT FOR A BST?

preorderupper boundone pass
WHAT TO LOOK FOR
  • 01THE NAIVE BUILD INSERTS FROM THE ROOT EACH TIME: O(n²)
  • 02EACH CALL CARRIES AN UPPER BOUND AND STOPS WHEN A VALUE EXCEEDS IT
  • 03THAT RETURN IS WHAT MARKS WHERE A SUBTREE ENDS
  • 04THE INDEX IS SHARED — A REJECTED VALUE IS NOT CONSUMED
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
56 / MECHANISM UNIT 10 · BSTPREORDER · CODE MIRRORED

THE BOUND CARRIES THE INFORMATION THE ARRAY LEFT OUT

For a BST, preorder alone fixes the tree. Each call carries an upper bound and returns when the next value exceeds it.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
57 / DRILL UNIT 10 · BUILD FROM PREORDER · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

What is the simplest correct way to build the tree, before any one-pass idea?

Insert each value from the root. O(n²) in the worst case, which is a sorted preorder: a chain.

DRILL 02 · TRANSFER

Preorder alone determines a binary search tree but not a general binary tree. What supplies the missing information?

The ordering. In a plain tree, preorder [1,2] could put 2 left or right; nothing says which.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
58 / DRILL UNIT 10 · BUILD FROM PREORDER · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

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 unread. The bound, not a search, marks where the subtree ends.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
59 / PROBLEM #11 · BOUNDS · MED

Construct a BST from a preorder traversal

MED bounds ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Build the BST whose preorder is this array”

INTUITION

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
  1. Keep a shared index into the preorder array
  2. Each call takes the next value only if it is under its bound
  3. Build the left subtree with the bound tightened to this node
  4. Build the right subtree with the bound inherited from the caller
  5. 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);
}
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
60 / PROBLEM #18 · BOUNDS · EASY

Convert Sorted Array to Binary Search Tree

EASY bounds ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Build a height-balanced BST from a sorted array”

INTUITION

The sorted array is the in-order. Make the middle the root, and do the same in each half.

STEPS
  1. build(lo, hi): if lo > hi, return null
  2. mid = (lo + hi) / 2; the root is nums[mid]
  3. Left subtree: build(lo, mid − 1)
  4. Right subtree: build(mid + 1, hi)
  5. The answer is build(0, n − 1)
BRUTEnone: any split is a BST, only the middle is balanced
→
OPTIMALO(n)
↕ SCROLL
Node* build(vector<int>& nums, int lo, int hi) {
    if (lo > hi) return nullptr;
    int mid = lo + (hi - lo) / 2;         // the middle value roots this range
    Node* root = new Node(nums[mid]);
    root->left  = build(nums, lo, mid - 1);
    root->right = build(nums, mid + 1, hi);
    return root;
}
Node* sortedArrayToBST(vector<int>& nums) {
    return build(nums, 0, (int)nums.size() - 1);
}
TIMEO(n)each element becomes one node
SPACEO(log n)recursion depth of a balanced tree
TRAP

Slicing the array each call. Copies cost O(n log n). Pass two indices.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
61 / INTRO UNIT 11 · SUCCESSOR WITHOUT A PARENT

UNIT 11 — SUCCESSOR WITHOUT A PARENT

The candidate trick again, on the in-order order

THE QUESTION THIS UNIT ANSWERS

WHERE IS THE SUCCESSOR OF A NODE WITH NO RIGHT CHILD?

successorpredecessorcandidate
WHAT TO LOOK FOR
  • 01IN-ORDER IS LEFT, NODE, RIGHT — THE SUCCESSOR IS THE NEXT LARGER
  • 02WITH A RIGHT CHILD: THE LEFTMOST OF THAT SUBTREE
  • 03WITHOUT ONE: THE LAST NODE WHERE THE WALK DOWN TURNED LEFT
  • 04SUCCESSOR IS STRICTLY GREATER — CEIL IS THE ONE THAT ALLOWS EQUAL
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
62 / MECHANISM UNIT 11 · BSTSUCC · CODE MIRRORED

THE CANDIDATE TRICK, APPLIED TO THE IN-ORDER ORDER

Walk from the root and record a candidate on every left turn. The last one is the successor, with or without a right child.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
63 / DRILL UNIT 11 · SUCCESSOR WITHOUT A PARENT · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

The successor is the next value in one traversal. Which, and in what order?

In-order is sorted. So the successor is just the next larger value.

DRILL 02 · TRANSFER

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 above the node.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
64 / DRILL UNIT 11 · SUCCESSOR WITHOUT A PARENT · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · BUG

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.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
65 / PROBLEM #12 · CANDIDATE · MED

Inorder Successor/Predecessor in BST

MED candidate ▶ SOLVE ON LEETCODE PREMIUM▶ SOLVE ON GEEKSFORGEEKSLC 285 is paid. The GeeksforGeeks problem is free and asks the same question.
SIGNAL — WHAT GIVES IT AWAY

“The next value after this one, in sorted order”

INTUITION

Walk from the root and record a candidate on every left turn. The last candidate is the successor.

STEPS
  1. Start with no candidate
  2. If the node's value is greater than the key, record it and go LEFT
  3. Otherwise it cannot be the successor — go RIGHT
  4. Return the last candidate recorded
  5. Predecessor is the mirror: record on smaller, then go right
BRUTEO(n) in-order into an array
→
OPTIMALO(h)
↕ SCROLL
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;
}
TIMEO(h)one comparison per level
SPACEO(1)no parent pointers needed
TRAP

Using >=. Successor is strictly greater; only ceil allows equal.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
66 / INTRO UNIT 12 · THE CONTROLLED STACK

UNIT 12 — THE CONTROLLED STACK

An in-order traversal you can pause, in O(h) space

THE QUESTION THIS UNIT ANSWERS

HOW DO YOU HAND BACK ONE SORTED VALUE AT A TIME WITHOUT FLATTENING?

iteratorleft spineamortised
WHAT TO LOOK FOR
  • 01THE INTERFACE IS next() AND hasNext() — IT MUST PAUSE
  • 02FLATTENING TO A VECTOR IS CORRECT AND COSTS O(n)
  • 03THE STACK HOLDS ONE LEFT SPINE: A NODE AND EVERYTHING DOWN ITS LEFT EDGE
  • 04PUSHED ONCE, POPPED ONCE · N CALLS COST O(N) IN ALL, SO O(1) PER CALL ON AVERAGE (AMORTISED)
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
67 / MECHANISM UNIT 12 · BSTITER · CODE MIRRORED

O(H) SPACE, BY REFUSING TO WALK AHEAD

The stack holds one left spine. next() pops a node and pushes the left spine of its right child. Space O(h), O(1) per call on average.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
68 / DRILL UNIT 12 · THE CONTROLLED STACK · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Which two operations must a BST iterator support?

next() and hasNext(). The walk must pause after each value until asked again.

DRILL 02 · TRANSFER

Flattening the tree into a sorted vector in the constructor also satisfies the interface. Why is it rejected?

Space. Flattening is easy but O(n), which throws the problem away.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
69 / DRILL UNIT 12 · THE CONTROLLED STACK · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Each node is pushed once and popped once across a full traversal. What does that make next()?

Amortised O(1). One next() can cost O(h), but each node is pushed only once overall.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
70 / PROBLEM #17 · INORDER · MED

Binary Search Tree Iterator

MED inorder ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“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
  1. Constructor: push the root and everything down its left edge
  2. next(): pop the top node; it is the smallest value not yet returned
  3. Push its right child and everything down that child's left edge
  4. Return the popped value
  5. 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 edge
        while (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 side
        return n->val;
    }
    bool hasNext() { return !st.empty(); }
};
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 / INTRO UNIT 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 / MECHANISM UNIT 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 / DRILL UNIT 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
74 / PROBLEM #13 · INORDER · MED

Merge 2 BST’s

MED inorder ▶ SOLVE ON LEETCODE▶ SOLVE ON GEEKSFORGEEKS
SIGNAL — WHAT GIVES IT AWAY

“All elements of two BSTs, in sorted order”

INTUITION

Two BSTs are two sorted lists: merge them like merge sort. Two iterators keep the space at the two heights.

STEPS
  1. Open an iterator on each tree
  2. Repeatedly take the smaller of the two current heads
  3. When one runs out, drain the other
  4. 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 removed
vector<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;
}
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 / INTRO UNIT 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 / MECHANISM UNIT 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 / DRILL UNIT 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 / DRILL UNIT 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

EASY inorder ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Do two distinct nodes sum to k?”

INTUITION

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
  1. Open a forward iterator (smallest first) and a reverse one
  2. Take one value from each end
  3. Sum too small: advance the low end
  4. Sum too large: retreat the high end
  5. 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) return true;
        if (a + b < k) a = lo.next();
        else b = hi.next();
    }
    return false;
}
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 / INTRO UNIT 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
81 / MECHANISM UNIT 15 · BSTRECOVER · CODE MIRRORED

A SORTED LIST WITH TWO SWAPS HAS ONE DIP, OR TWO

In-order should only rise. Far apart: two dips. Adjacent: one dip, and both culprits are in it.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
82 / DRILL UNIT 15 · RECOVER — TWO VIOLATIONS · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

What does the problem guarantee about the damage to the tree?

Exactly two, swapped. So the sorted order falls in at most two places.

DRILL 02 · TRACE

In-order of the damaged tree reads 12 4 6 8 10 2 14. Which two values must be swapped back?

12 and 2. Two dips, 12 → 4 and 10 → 2: the first dip's first value and the last dip's second.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
83 / DRILL UNIT 15 · RECOVER — TWO VIOLATIONS · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRANSFER

Your code handles two dips correctly and fails a small test. What shape did you miss?

Adjacent nodes give ONE dip. Both culprits come from that single fall.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
84 / PROBLEM #15 · INORDER · MED

Correct BST with two nodes swapped

MED inorder ▶ SOLVE ON LEETCODE
SIGNAL — WHAT GIVES IT AWAY

“Exactly two nodes were swapped — put them back”

INTUITION

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
  1. Walk in-order, remembering the previously visited node
  2. A value smaller than the previous one is a dip
  3. First dip: record the previous node as first, this one as second
  4. Any later dip: overwrite second with this node
  5. 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);
}
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 / INTRO UNIT 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
86 / MECHANISM UNIT 16 · BSTLARGEST · CODE MIRRORED

THE PARENT CANNOT JUDGE ITSELF UNTIL BOTH CHILDREN REPORT

One postorder pass: each call returns min, max, size and verdict. Node 10 fails even though both its sides are BSTs.

THE TREE
PANEL
RESULT
CODE MIRROR
INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
87 / DRILL UNIT 16 · LARGEST BST INSIDE A TREE · 1 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · RECALL

Tree [10,5,15,1,8,7]: every node is fine with its own parent. Why is the whole tree not a BST?

The 7 under 15. A fine left child of 15, but it is in 10's right subtree and smaller than 10.

DRILL 02 · TRANSFER

Why must this be post-order rather than pre-order?

Information flows up. A node needs its children's max, min and verdicts first.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
88 / DRILL UNIT 16 · LARGEST BST INSIDE A TREE · 2 OF 2

CHECK — CAN YOU ANSWER IT WITHOUT LOOKING BACK?

DRILL 01 · TRACE

Tree [10,5,15,1,8,7]. What is the largest BST subtree, and how big?

The subtree at 5 (5, 1, 8), size 3. The one at 15 is a BST too, but has only 2 nodes.

INVARIANT · BST · Binary Search Trees · BINARY SEARCH TREES
89 / PROBLEM #16 · BOUNDS · MED

Largest BST in Binary Tree

MED bounds ▶ SOLVE ON LEETCODE PREMIUM▶ SOLVE ON GEEKSFORGEEKSLC 333 is paid. The GeeksforGeeks problem is free and asks for the same size.
SIGNAL — WHAT GIVES IT AWAY

“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
  1. Recurse into both children first
  2. A null subtree is a BST of size 0. Its min is +inf and its max is -inf, so it never blocks its parent
  3. This node roots a BST iff both children do AND its value fits between them
  4. If so, its size is left + right + 1 — update the best
  5. 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; }
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 / RECALL RETRIEVAL, 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 / RECALL RETRIEVAL, 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 / RECALL RETRIEVAL, 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 / TRAPS PLAUSIBLE, 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 / CHEATSHEET REVISION 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 / CLOSE 14 · 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.

00%
OF THIS DECK SOLVED
← ALL TOPICSTHE SHELFSTEP 13 · BINARY TREES

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
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.