One promise, two consequences. This sub-variant is the first of them.

1. 1

   The promise. For every node, the entire left subtree is smaller and the entire right subtree is larger. Note entire — it is a claim about subtrees, not about parent-child pairs.

2. 2

   So one comparison discards half. If the target is smaller than the current node, it cannot be anywhere in the right subtree. That is a whole branch eliminated by a single test, which is exactly binary search.

3. 3

   LCA needs no upward pass. If both targets are smaller than the current node, both live in the left subtree, so the meeting point is also down there. Same for larger. Descend while they agree.

4. 4

   The first disagreement is the answer. When one target is smaller and the other larger — or one is the current node — the paths diverge here. This node is the lowest that contains both.

The thesis for every template in this pattern: every one of them is the same descent. Compare, discard a side, recurse or loop. If a BST solution of yours visits both children unconditionally, you have written a binary-tree solution and thrown the ordering away — which is sometimes right (see C) and usually wrong.

Write search iteratively. The recursion is pure tail recursion and Java will not eliminate it, so the loop is strictly better — O(1) space instead of O(h).

Using the general LCA on a BST is a wrong answer even when it is correct. It runs in O(n) and misses the entire point of the question, which is whether you noticed the ordering.

Both targets are in the left subtree until they are not. Watch the descent stop at the first disagreement.

Answer 2 — reached in two comparisons on a seven-node tree. Node 2 is itself one of the targets and the other is beneath it, which on a plain binary tree needed the careful two-reading argument of Pattern 2 G. Here it falls out of the targets no longer agree on a direction, with no case analysis at all.

• Name what the ordering bought, per problem. The gate asks exactly that. For search: half the tree per comparison. For LCA: the entire upward pass disappears.
• Iterative search is the better answer. Tail recursion is not optimised in Java, so the loop saves O(h) stack for no cost in clarity.
• The promise is about subtrees, not parents. Worth internalising here, because sub-variant B exists entirely because people forget it.
• Reaching for Pattern 2's LCA on a BST is a tell. It signals you are treating the BST as a plain tree. Correct, O(n), and the wrong answer to the question being asked.

• ✗Using the general LCA on a BST

  Symptom: correct but O(n), and it misses the point of the question.

  Prevention: If it is a BST, descend by comparison.

• ✗Writing search recursively

  Symptom: O(h) stack for a pure tail call Java will not eliminate.

  Prevention: Use a loop.

• ✗Visiting both children unconditionally

  Symptom: you have written a binary-tree solution and discarded the ordering.

  Prevention: One comparison must eliminate a side. If it does not, re-read the bounds.

• ✗Assuming parent-child ordering is the property

  Symptom: accepts trees that are not BSTs — see sub-variant B.

  Prevention: The promise covers the entire subtree, so it constrains every ancestor.

One counterexample, then the two standard repairs — which are worth knowing as a pair.

1. 1

   The property is about subtrees. Everything in the right subtree of 5 must exceed 5 — not just 5's immediate right child. A node three levels down is still bound by that constraint.

2. 2

   So parent comparison accepts invalid trees. In the diagram, 3 is a valid left child of 4, and 4 is a valid right child of 5 — yet 3 sits in 5's right subtree while being smaller than 5. Every local check passes.

3. 3

   The range fix, top-down. Carry (low, high). Descending left replaces high with the node's value; descending right replaces low. The bounds narrow monotonically, so every ancestor's constraint is still enforced at the bottom.

4. 4

   The inorder fix, bottom-up. A tree is a BST exactly when its inorder traversal is strictly increasing. Keep one prev node and compare. No arithmetic, and it extends to any is this sequence sorted question.

The sentence that defines the pattern's failure mode: the promise is about whole subtrees, not about parent-child pairs. A node can be larger than its parent and still violate the BST property.

Integer.MIN_VALUE sentinels are a bug, not a shortcut. A node may legitimately hold that value, and the comparison then fails on a perfectly valid tree. Use long bounds, or the nullable prev node of the inorder version.

State the duplicate policy before coding. LeetCode's BSTs are strict, so <= where < belongs silently accepts duplicates. It is a one-character difference and a real correctness decision.

The counterexample from above. Every parent-child pair is fine; the inherited range catches it anyway.

Not a BST. Row 4 is the whole lesson: node 3 is a perfectly legal left child of 4, and a parent-only check waves it through. The inherited low = 5 — set three levels up, when the descent turned right at the root — is what catches it. Note also that row 3 already fails; the example is drawn so that both the immediate and the distant violation are visible.

• Know both solutions, deliberately. The gate asks for LC 98 both ways. They are not redundant: the range form is top-down arithmetic, the inorder form is a bottom-up scan that generalises further.
• The sentinel bug is worth naming. Node values may be Integer.MIN_VALUE is a concrete reason, not a stylistic preference. The gate asks you to explain it.
• Bounds narrow monotonically. That monotonicity is what makes the top-down version correct — each step can only tighten, never loosen, so ancestor constraints survive to the leaves.
• The inorder form has a wider reach. Anything phrased as is this traversal sorted becomes the same three lines with a different predicate.

• ✗Validating against the parent only

  Symptom: accepts trees that are not BSTs.

  Prevention: The property is about ancestors, not parents. Inherit (low, high).

• ✗Integer.MIN_VALUE / MAX_VALUE as sentinels

  Symptom: fails on trees containing those exact values.

  Prevention: Use long bounds, or a nullable prev node in the inorder version.

• ✗<= instead of <

  Symptom: accepts duplicates.

  Prevention: LeetCode's BSTs are strict. State the duplicate policy before coding.

• ✗Comparing prev by value when it may be unset

  Symptom: a null dereference on the leftmost node.

  Prevention: prev starts null and the first comparison is skipped — that is what makes the nullable form work.

Three problems, one mechanism, and one complexity argument that has to be made explicitly.

1. 1

   Inorder over a BST is sorted. Left subtree, node, right subtree — and everything left is smaller, everything right larger. The sequence comes out ascending by construction.

2. 2

   So adjacency in the traversal is adjacency in sorted order. The minimum difference between any two values is therefore between inorder-adjacent nodes only. Comparing all pairs is O(n^2) for information a single scan already has.

3. 3

   One prev node makes it a scan. Hold the previously visited node and compare on arrival. That is the whole machinery for LC 530 and LC 99.

4. 4

   LC 99 needs two inversions, not one. If the swapped nodes are adjacent there is one inversion; if they are far apart there are two. Take first from the first inversion's left element and second from the last inversion's right element, and both cases are covered.

The sentence the gate asks for unprompted: the minimum difference is between inorder-adjacent nodes. Once that is said, LC 530 is a three-line scan and comparing all pairs stops being tempting.

LC 230's early exit is the point, not an optimisation. Stop as soon as the counter reaches k. Without it you have sort the tree and index it, which answers the question with the wrong complexity story — and the natural follow-up is the subtree-size augmentation, which makes repeated queries O(h).

Reverse inorder is a descending scan for free. Right, node, left — used by LC 538 to accumulate a running suffix sum without any extra structure.

The inorder sequence should be 1 2 3 4. Nodes 3 and 1 have been swapped, so the traversal reads 3 2 1 4 — two separate inversions.

Swap 3 and 1 and the tree is repaired. Row 3 is why one inversion is not enough: had you stopped after the first, you would swap 3 and 2 and produce 2 3 1 4, which is still broken. When the swapped nodes are adjacent there is only one inversion, and first and second both come from it — which is why the same rule covers both cases.

• This is the sub-variant where visiting both children is right. Everywhere else in this pattern that means you threw the ordering away. Here it is the point, and knowing the difference is what §3.1 is warning about.
• prev is the whole technique. One nullable node variable turns a tree walk into a sorted-sequence scan. Recognising that collapses three problems into one idea.
• Say the adjacency claim before writing LC 530. The minimum gap is between inorder-adjacent nodes. The gate asks for it unprompted, and it is what rules out the O(n^2) approach.
• The early exit changes the complexity story. Without it, LC 230 is a full traversal. With it — and with the subtree-size follow-up — it is a genuinely different answer.

• ✗Comparing all pairs for the minimum difference

  Symptom: O(n^2) for information a single inorder scan already contains.

  Prevention: In a BST the minimum gap is between inorder-adjacent nodes only.

• ✗kthSmallest without an early exit

  Symptom: a full O(n) traversal, and a bad follow-up conversation.

  Prevention: Stop as soon as the counter reaches k; mention the subtree-size augmentation.

• ✗Recovering a swapped BST by tracking one inversion

  Symptom: wrong whenever the swapped nodes are not adjacent.

  Prevention: first from the first inversion, second from the last.

• ✗Materialising the inorder list

  Symptom: O(n) extra space for a scan that needs one variable.

  Prevention: Hold prev and compare on arrival.

Two cases. The first is easy and the second is the reason this sub-variant exists.

1. 1

   Turning right tells you nothing useful. Going right means the current node is smaller than the target. A smaller node can never be the successor, so it is discarded.

2. 2

   Turning left records a candidate. Going left means the current node is larger than the target. It is therefore an upper bound — and each subsequent left turn is a tighter one, so the last is the best.

3. 3

   Case 1: the target has a right subtree. Then the successor is inside it — specifically its minimum, the leftmost node. That is closer to the target than any ancestor could be.

4. 4

   Case 2: no right subtree. Nothing below the target is larger, so the answer must be above it — and it is exactly the deepest ancestor from which the descent turned left.

The sentence to have ready: the successor is the last node from which you turned left — the deepest ancestor still greater than the target. It is not the node you stopped on.

Predecessor is the exact mirror. Remember right turns instead, and if the target has a left subtree take that subtree's maximum.

LC 173's iterator is this operation repeated. A stack of not-yet-returned ancestors is the same remembered left turns idea, made persistent between calls — see Pattern 1 B.

The target is a leaf, so the answer cannot be below it. Watch the remembered column.

Successor is 6. The descent stopped at node 5, and 5 has no right child — so the answer had to come from the remembered variable. Notice how row 3 tightened the bound from 8 to 6: each left turn is a better upper bound than the last. Read the answer off the stopping node instead and you get nothing at all.

• The answer is in a variable, and say so. The gate asks you to explain why it is the last left-turn rather than the stopping node. That framing is the whole sub-variant.
• Hand-trace a target with no right child. The gate names this case specifically, because it is the one where the naive reading fails.
• Each left turn tightens the bound. Which is why the last one is the answer and not the first. Worth stating — it explains why a single variable suffices.
• Predecessor is not a separate skill. Mirror the turns and the subtree. Deriving it from successor rather than memorising it separately is the sign the idea has landed.

• ✗Reading the successor off the stopping node

  Symptom: wrong answer whenever the node has no right child.

  Prevention: The answer is the last node you turned left from; track it in a variable.

• ✗Forgetting the right-subtree case

  Symptom: you return a distant ancestor when a much closer node exists below.

  Prevention: If the target has a right subtree, the successor is that subtree's minimum.

• ✗Remembering the first left turn instead of the last

  Symptom: an upper bound, but not the tightest one.

  Prevention: Overwrite on every left turn. The deepest one wins.

• ✗Materialising the inorder sequence to find it

  Symptom: O(n) time and space for an O(h) operation.

  Prevention: The descent already carries the information.

Two easy cases and one that people get wrong in a specific, delayed-failure way.

1. 1

   Insertion is always at a leaf. Descend by comparison until you fall off the tree. The null position you reach is exactly where the value belongs, so there is no restructuring to do.

2. 2

   Delete, no children. Return null. The parent's assignment does the detaching for you.

3. 3

   Delete, one child. Return that child. Everything in it already satisfies the ordering relative to the parent, because it satisfied it relative to the node being removed.

4. 4

   Delete, two children. You cannot simply return one child — the other would be orphaned. So copy the inorder successor's value into this node (it is the smallest value larger than everything on the left, so the ordering still holds), then delete that successor from the right subtree recursively. The successor has at most one child, so that deletion is one of the easy cases.

Why the two-child case recurses instead of splicing: copy the successor's value, then recursively delete the successor. Recursing keeps the invariant at every level; splicing pointers by hand produces a corrupt tree that fails on the next operation rather than this one.

The successor always has at most one child. It is the leftmost node of the right subtree, so it has no left child by definition — which is why the recursive delete terminates in one of the easy cases and cannot recurse indefinitely.

The predecessor works equally well. Copying the largest value from the left subtree is symmetric and equally correct; pick one and be consistent.

Delete 5, which has both children. Watch the value get copied down and the successor removed from below.

Final tree: root 6, left subtree 3(2,4), right child 7. Step 4 is the reason for recursion — the successor had a right child, and splicing pointers by hand would have dropped it. Because the successor is the leftmost node of the right subtree, it can never have a left child, so the recursive call always lands in the zero- or one-child case.

• The return-the-subtree idiom is the reusable part. node.left = delete(node.left, key) makes the parent rewire itself. It removes parent pointers, root special-cases and most of the bug surface in one move.
• Justify the recursive delete, do not just perform it. The gate asks specifically for that justification rather than a pointer splice.
• Say why the successor is easy to remove. It is the leftmost node of the right subtree, so it has no left child. That is what guarantees termination.
• Corruption here is delayed. A bad splice produces a tree that looks fine and fails on the next operation, which is what makes it worth getting right the first time.

• ✗Deleting a two-child node by splicing pointers

  Symptom: corrupt tree on the next operation, not this one.

  Prevention: Copy the successor's value, then recursively delete the successor.

• ✗Taking the successor from the wrong side

  Symptom: the ordering breaks — you need the smallest value larger than the left subtree.

  Prevention: Inorder successor = leftmost node of the right subtree.

• ✗Maintaining parent pointers to rewire

  Symptom: extra state and a root special-case for no benefit.

  Prevention: Return the new subtree root and let the parent assign it.

• ✗Assuming insertion may need restructuring

  Symptom: unnecessary complexity.

  Prevention: Insertion is always at a null leaf. Descend, attach, done.

Two constructions. The second is a genuinely nice reuse of an earlier sub-variant.

1. 1

   Sorted plus balanced determines the root. For the tree to be height-balanced, the two subtrees must hold equal counts. The only element that splits a sorted array into equal halves is the middle one.

2. 2

   Each half is the same problem. Everything before the middle is smaller (so it is the left subtree) and everything after is larger. Recurse identically, and the result is balanced by construction.

3. 3

   LC 1008 turns validation into construction. In sub-variant B the range (low, high) checked each node. Here it decides whether the next value in the stream belongs in this subtree at all.

4. 4

   Which gives O(n). Consume values while they fit inside the current bounds; return the moment one does not. Each value is examined a constant number of times, so the whole preorder stream is processed once.

The reuse worth naming: LC 1008 is the range trick from LC 98 running forward over the preorder stream — consume values while they fit inside (low, high), and return as soon as one does not.

Never build from sorted input by repeated insertion. Every value is larger than the last, so every insert descends right and the tree degenerates into a linked list — O(n^2) to build and O(n) per subsequent operation.

The cursor is shared, exactly as in Pattern 2 H and I. The left subtree consumes an unknown number of preorder values, so the right subtree must start after all of them.

[-10, -3, 0, 5, 9]. The middle element becomes the root at every level, so balance is automatic.

Height 3, perfectly balanced, in O(n). Compare against inserting -10, -3, 0, 5, 9 one at a time: each value exceeds everything already present, so every insert walks the full right spine and the result is a five-node chain built in O(n^2). The sorted order was carrying the shape information all along.

• Sorted input is shape information, not just data. That reframing is what makes LC 108 obvious and repeated insertion visibly wrong.
• Name the reuse in LC 1008. The LC 98 range trick, running forward. The gate asks for exactly that explanation, and it is what turns an O(n log n) insert-based solution into O(n).
• Either middle works for even counts. Left or right of centre both give a valid height-balanced tree. Say so rather than agonising.
• The degenerate case is worth stating unprompted. Inserting sorted data one at a time gives a linked list is a good instinct to demonstrate.

• ✗Building from a sorted array by inserting one at a time

  Symptom: degenerates to a linked list, O(n^2).

  Prevention: Recurse on the middle element.

• ✗Rebuilding index ranges by copying subarrays

  Symptom: O(n log n) time and O(n log n) space for no benefit.

  Prevention: Pass (lo, hi) indices into the original array.

• ✗Copying the preorder cursor per frame in LC 1008

  Symptom: subtrees built from the wrong position in the stream.

  Prevention: The cursor is shared — a field or an int[1].

• ✗Assuming unsorted input can use this

  Symptom: the middle element is meaningless without an ordering.

  Prevention: Sort first, or accept repeated insertion.

Pruning is straightforward until LC 669, where the obvious move deletes valid data.

1. 1

   Pruning on the sum. If node.val < low, everything in the left subtree is also below low, so it cannot contribute — recurse right only. Symmetrically for > high.

2. 2

   Trim looks similar and is not. The temptation is to return null for any node outside the range, mirroring the pruning logic.

3. 3

   But out-of-range does not mean the subtree is empty. If node.val < low, its left subtree is entirely below low and can go — but its right subtree may contain values inside the range.

4. 4

   So return the trimmed surviving side. The replacement for an out-of-range node is the trimmed subtree on the side that could still hold valid values. Returning null throws those away silently.

The standard wrong answer, and why: when a node is below low, its entire left subtree is below low too — so the replacement is the trimmed right subtree, not null. Returning null here silently deletes valid nodes.

LC 538 gets a descending scan for free. Reverse inorder — right, node, left — visits values largest-first, so a running suffix sum needs no extra structure at all.

If both children are always visited, the bounds are not doing anything. That is the self-check for this sub-variant: one comparison should eliminate a side, and if it does not, re-read the bounds.

Node 1 is below the range. Return null for it and you delete nodes 2 and 3, which are perfectly valid.

Correct result: root 3 with right child 4 and no left child — because trimming node 1 returned its right subtree (node 2), which then trimmed to null in its own right. The naive version reaches the same answer here only by luck; add a node valued 3 under 2 and the naive version deletes it while the correct version keeps it. That is the counterexample the gate asks for.

• The self-check is one sentence. Did a comparison eliminate a side? If both children are always visited, you are paying O(n) for a structure that offered O(h + k).
• Trim is not pruning, despite looking like it. Pruning skips work; trimming rebuilds. Returning null conflates the two and loses data.
• Have the counterexample ready. The gate asks for a concrete four-node tree. Abstract reasoning is not what it is testing.
• Reverse inorder is a free descending scan. Worth remembering as a general trick, not just for LC 538.

• ✗Recursing into both children in a range query

  Symptom: O(n) where O(h + k) was asked for.

  Prevention: One comparison must eliminate a side; if it does not, re-read the bounds.

• ✗trim returning null for an out-of-range node

  Symptom: silently deletes in-range descendants.

  Prevention: Return the trimmed subtree on the surviving side.

• ✗Trimming only one level

  Symptom: out-of-range nodes survive deeper in the tree.

  Prevention: The returned subtree must itself be trimmed — the recursion does this if you return its result.

• ✗Using forward inorder for a descending accumulation

  Symptom: you need the whole sequence before you can start.

  Prevention: Reverse inorder gives descending order directly.

A short sub-variant, because the skill is recognition rather than implementation.

1. 1

   Hash maps cannot answer neighbour queries. What is the largest key at most x? requires an ordering. A hash map has none, so the question costs a full scan.

2. 2

   A balanced BST answers them in O(log n). floorKey, ceilingKey and the range views are exactly the descent from sub-variant A, with rebalancing handled for you.

3. 3

   Mutation is what rules out sorting once. If the collection never changed you could sort an array and binary search it. An ordered container earns its keep precisely when inserts and deletes are interleaved with queries.

4. 4

   LC 653 makes the connection explicit. Two converging pointers over a forward and a reverse BST iterator is the sorted-array two-pointer template, with the array replaced by two O(h)-space cursors. Same algorithm, different backing store.

The connection the gate asks you to name: LC 653 is converging two pointers — sub-variant A of Two Pointers — with the sorted array replaced by a forward and a reverse BST iterator. Solving it with a hash set works and misses the point.

The iterators are the ones from Pattern 1 B. A paused inorder walk gives the forward cursor; a paused reverse inorder gives the backward one. Each is O(h) space and amortized O(1) per step.

This is where the two documents meet. The ordered-multiset sliding window uses the same structure to maintain a window median — a BST used as a moving aggregate rather than a static container.

Target 9. The forward iterator yields ascending values, the reverse one descending — exactly the two ends of a sorted array.

Found immediately here, but the shape is the point: had the sum been too small the forward cursor would advance, and too large the reverse cursor would retreat — identical to converging pointers on a sorted array. The two iterators cost O(h) space each, versus O(n) for a hash set, and the discard argument is the one from Two Pointers A, unchanged.

• Recognition is the whole skill here. Do I need neighbour queries on a changing collection? If yes, ordered container. If no, a hash map is simpler and faster.
• Name the two-pointer correspondence. The gate asks you to solve LC 653 with two iterators and name the sub-variant it corresponds to. The naming is half the exercise.
• Know the API, not just the concept. floorKey, ceilingKey, higherKey, subMap. Reaching for the right method is what makes this practical rather than theoretical.
• This is the bridge out of the topic. Treating BSTs as a tool rather than a subject is exactly what the final gate is checking.

• ✗Solving LC 653 with a hash set

  Symptom: correct, O(n) space, and it ignores the structure entirely.

  Prevention: Two iterators, O(h) space each. The gate asks for that version specifically.

• ✗Using an ordered container for plain membership

  Symptom: O(log n) where O(1) was available.

  Prevention: A hash map is simpler unless you need ordering.

• ✗Hand-rolling a balanced BST

  Symptom: rotation bugs, for functionality the standard library already provides.

  Prevention: TreeMap / TreeSet unless the problem explicitly forbids them.

• ✗Sorting once when the collection mutates

  Symptom: the sorted snapshot goes stale after the first insert.

  Prevention: An ordered container maintains the invariant across mutations.