DSA sheet · Trees · Binary Search Tree pattern

Recover BST

Someone took a correct BST and, by mistake, swapped the values of exactly two nodes. We have to find those two and swap them back. The teacher builds the answer in three steps: a brute force that sorts (O(n log n)), a better one that skips sorting (O(n), but with an extra array), and the best one that just remembers the previous node during an inorder walk (O(n), no array).

Why it matters: this is the clearest example of "inorder of a BST is sorted" being used as a tool. Once you see the tree as a sorted list with two items swapped, the problem becomes easy.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the conditions from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: collect, sort, refill
• Part B · Better: inorder array, find the two, swap
• Part C · Optimal: inorder with a previous pointer
• Part D · Revision page

Part 0 · Before starting

What is a tree node?

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

The BST property

In a Binary Search Tree, for every node: all values in its left subtree (the left child and everything below it) are smaller than the node, and all values in its right subtree are bigger. The rule covers all nodes below, not only the direct children.

      6
     / \
    3   8
   / \
  1   4

      6
     / \
    3   8
   / \
  1   7

In the second tree, 7 is fine as the right child of 3 (7 > 3). But it's in the left subtree of 6, so it must be smaller than 6. It isn't, so this is not a BST.

Inorder traversal, and why it gives a sorted list for a BST

Inorder visits a tree in this order: left subtree → the node → right subtree, doing the same thing inside each subtree.

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)    # 1. everything on the left
    out.append(node.val)       # 2. the node itself
    inorder(node.right, out)   # 3. everything on the right

Why sorted? At any node, inorder first lists its whole left subtree, which are all smaller values. Then the node. Then its whole right subtree, which are all bigger values. So at every node: smaller things, then me, then bigger things. The same holds inside the left part and the right part, so the whole list comes out in increasing order. For the BST above, inorder gives 1 3 4 6 8.

Why swapping two values breaks the order in one or two places

Take a sorted list 1 2 3 4 5 6. Swap two values and look for places where a number is bigger than the next one (call it a "drop"):

• swap neighbours 3 and 4 → 1 2 4 3 5 6 → one drop (4 > 3)
• swap far apart 2 and 5 → 1 5 3 4 2 6 → two drops (5 > 3, and 4 > 2)

We'll come back to this. It's the heart of Parts B and C.

Part A · Brute force: collect, sort, refill

LeetCode 99

1The question in simple words

You get the root of a BST in which exactly two nodes have had their values swapped. Fix the tree in place (don't build a new one, and the function returns nothing) by putting the two values back where they belong. The shape of the tree stays the same. Only two values move.

      3
     / \
    1   4
       /
      2

      2
     / \
    1   4
       /
      3

      1
     /
    3
     \
      2

In the first tree, 2 is inside the right subtree of 3, yet smaller than 3. That breaks the rule. Swap 3 and 2 back and every node is in its place. In the third tree (LeetCode Example 1), 1 and 3 were swapped. The fix is root 3, left child 1, and 1's right child 2.

2What the constraints tell us

• Number of nodes: 2 to 1000 (10³). That's small. Even O(n²) would be about 10⁶ steps, far below the ~10⁸ that causes TLE. So all three approaches pass. We improve them for the interview, not because the judge forces us to.
• At least 2 nodes always: there really are two nodes to swap, so first and second will always be found.
• Values: the full 32-bit range, −2³¹ to 2³¹−1. Normally that would make you worry about overflow. But here we never add or multiply values. We only compare and swap them, so a value can never grow past its type. No long needed (and in Python ints never overflow anyway).

3Intuition

The first idea that should come to mind for any BST question is inorder, because inorder of a correct BST is sorted. For our tree, inorder gives 1 3 2 4. It isn't sorted, because two values were swapped. The correct tree would give 1 2 3 4.

Brute force idea: get the values, sort them, and write them back into the tree in inorder order. The smallest value goes to the first node inorder visits, the next value to the next node, and so on. After that the tree's inorder is sorted, so it's a correct BST again.

4Building the logic

Collecting: does the order matter?

No. Since we sort right after, we can collect the values with any traversal: preorder, inorder or postorder. The teacher points this out. (We use preorder below just to show it doesn't matter.)

Refilling: this one must be inorder

We walk the tree in inorder and keep a pointer index into the sorted list. Each time inorder reaches a node, we overwrite its value with sorted_values[index] and move the pointer forward by one. Inorder visits nodes from "smallest place" to "biggest place", so the sorted values land exactly where they belong.

For our tree: inorder reaches 1 first → write 1. Then the root → write 2. Then 4's left child → write 3. Then 4 → write 4. Some writes don't change anything (1 stays 1), and that's fine.

5Approach steps

1. Traverse the tree (any order) and collect all values in a list.
2. Sort the list.
3. Do an inorder walk with a shared index = 0. At each node: node.val = values[index], then index += 1.

6Code (Python)

class Solution:
    def recoverTree(self, root):
        values = []
        self.collect(root, values)     # any traversal is fine
        values.sort()                  # O(n log n)
        self.index = 0
        self.refill(root, values)      # must be inorder

    def collect(self, node, values):   # preorder here, on purpose
        if node is None:
            return
        values.append(node.val)
        self.collect(node.left, values)
        self.collect(node.right, values)

    def refill(self, node, values):    # inorder: left, node, right
        if node is None:
            return
        self.refill(node.left, values)
        node.val = values[self.index]
        self.index += 1
        self.refill(node.right, values)

7Code line by line

8Dry run

Tree: root 3, left 1, right 4, and 4's left is 2.

1. collect (preorder) → [3, 1, 4, 2]
2. sort → [1, 2, 3, 4]
3. refill, inorder: go left from 3 to 1. Node 1 ← values[0] = 1, index = 1.
4. Back at the root (old 3) ← values[1] = 2, index = 2.
5. Go right to 4, then left to its child (old 2) ← values[2] = 3, index = 3.
6. Back at 4 ← values[3] = 4. Done. The tree is root 2, left 1, right 4 with left child 3 ✓

9Complexity & remember

• Time O(n log n): O(n) to collect + O(n log n) to sort + O(n) to refill. The biggest term wins, so O(n log n).
• Space O(n): the list of all values (plus O(h) for the recursion).

Part B · Better: inorder array, find the two, swap

1The question

Same as Part A. Now we ask the teacher's question: the input was a BST with only two values swapped, so do we really need to sort?

2Constraints

Same as Part A. n ≤ 1000, so any of these pass. We're improving for the interview.

3Intuition

If we collect the values in inorder, the list is already sorted except for the two swapped values. So we don't need to sort the whole thing. We just find the two values that are out of place by walking the list once and comparing each value with the one before it, swap those two in the list, and refill the tree.

4Building the conditions from examples

Walk with index i from 1 and check: is values[i] bigger than values[i-1]? If yes, this spot is in order. If not, we found a "drop", a spot where the order breaks.

• Example A: 1 3 2 4. At i = 2: 2 < 3 → a drop. The two out of place are 3 (the one before the drop) and 2 (the one at the drop). There's only one drop, because the two swapped values were neighbours in the list.
• Example B (the teacher's second tree, worked through in Part C): 1 8 4 6 7 3 10. First drop at 8 → 4, second drop at 7 → 3. The two out of place are 8 (the "before" value at the first drop) and 3 (the "after" value at the last drop).

Part C explains with both trees why we must keep scanning after the first drop.

5Approach steps

1. Inorder walk → list values (almost sorted).
2. Scan i = 1 … n−1. At each drop (values[i-1] > values[i]): if it's the first drop, remember x = i-1. Always set y = i.
3. Swap values[x] and values[y]. Now the list is fully sorted.
4. Refill the tree in inorder, the same as Part A.

6Code (Python)

class Solution:
    def recoverTree(self, root):
        values = []
        self.inorder(root, values)          # almost sorted
        x = y = -1
        for i in range(1, len(values)):
            if values[i - 1] > values[i]:  # a drop
                if x == -1:
                    x = i - 1               # first drop: the bigger one
                y = i                       # every drop: the smaller one
        values[x], values[y] = values[y], values[x]
        self.index = 0
        self.refill(root, values)

    def inorder(self, node, values):
        if node is None:
            return
        self.inorder(node.left, values)
        values.append(node.val)
        self.inorder(node.right, values)

    def refill(self, node, values):
        if node is None:
            return
        self.refill(node.left, values)
        node.val = values[self.index]
        self.index += 1
        self.refill(node.right, values)

7Code line by line

8Dry run (hand table)

Tree B (root 6, left 8 with children 1 and 4, right 3 with children 7 and 10). Inorder = 1 8 4 6 7 3 10.

Swap values[1] and values[5] → 1 3 4 6 7 8 10 ✓ sorted. The refill puts 3 where 8 was and 8 where 3 was.

9Complexity & remember

• Time O(n): O(n) inorder + O(n) scan + O(n) refill = 3·O(n), which is still O(n). Much better than O(n log n).
• Space O(n) for the list.

Part C · Optimal: inorder with a previous pointer

1The question

Same problem. Goal: one inorder walk, no list, and swap the two nodes' values directly.

2Constraints

Same as before. Values are only compared and swapped, never added, so there's no overflow worry.

3Intuition: you only ever compared neighbours

Look at Part B again. While scanning the list we only ever looked at two values: values[i-1] and values[i], the previous one and the current one. So why store the whole list? During the inorder walk itself, we can remember the node inorder visited just before this one. Call it prev. Then, right at the moment inorder "visits" a node, compare it with prev. That's the same i−1 vs i check, done on the fly.

And instead of remembering positions, we remember the nodes themselves (first and second). At the end we swap their .val directly. No second walk to refill.

4Building the conditions from examples

Where does the check go?

Think of plain inorder. The line where we used to append the value to the list, between the left call and the right call, is exactly the moment we "visit" the node. Our new logic goes right there. The base case and the left and right calls stay unchanged.

Condition 1: prev must exist

The very first node inorder visits (the leftmost one) has nobody before it. prev is still None, so there's nothing to compare. Just make this node the prev and move on.

Condition 2: a drop means prev.val > root.val

In a correct BST, every node inorder visits is bigger than the one before it. If prev.val > root.val, the order broke right here.

What to save at a drop: first = prev, second = root

• first is set only at the first drop (only if it's still None), and it's the previous node, the bigger value that moved too early.
• second is set at every drop, and it's the current node (root), the smaller value that moved too late.

Example A: the swapped pair are neighbours (one drop)

      3
     / \
    1   4
       /
      2          inorder: 1 3 2 4

Visit 1: no prev → prev = 1. Visit 3: 1 > 3? no → prev = 3. Visit 2: 3 > 2? yes, a drop → first = prev = 3, second = root = 2 → prev = 2. Visit 4: 2 > 4? no. End. Swap 3 and 2 ✓.

Example B: the swapped pair are far apart (two drops)

        6
      /   \
     8     3
    / \   / \
   1   4 7   10

        6
      /   \
     3     8
    / \   / \
   1   4 7   10

Inorder: 1 8 4 6 7 3 10. After 1 comes 8, fine. Then suddenly 4, smaller than 8: the first drop. If we stopped here and swapped 8 and 4, we'd get root 6, left 4 (with children 1 and 8)… and now 8 is in the left subtree of 6 but bigger than 6. Still not a BST. So the pair (8, 4) was wrong.

Keep going: 4, 6, 7, all increasing, and then suddenly 3, smaller than 7. A second drop. The real culprit on this end is 3. So the pair is 8 and 3. Swap them and the tree is a correct BST.

Update prev every time

After the check, whether there was a drop or not, set prev = root. The next node inorder visits will compare itself with this one.

While writing the declarations, the teacher first names the third variable temp, then corrects it to prev. The temp she needs for the swap is a separate, plain integer at the end.

5Approach steps

1. Set prev = first = second = None.
2. Do inorder. At each node (between the left and right calls): if prev exists and prev.val > root.val → if first is None, set first = prev; always set second = root. Then prev = root.
3. After the walk, swap first.val and second.val using a temp variable.

6Code (Python)

import sys
sys.setrecursionlimit(10000)    # a 1000-node chain is 1000 calls deep

class Solution:
    def recoverTree(self, root):
        self.prev = None
        self.first = None
        self.second = None
        self.inorder(root)
        temp = self.first.val                  # swap the two values
        self.first.val = self.second.val
        self.second.val = temp

    def inorder(self, root):
        if root is None:
            return
        self.inorder(root.left)
        if self.prev is not None and self.prev.val > root.val:
            if self.first is None:
                self.first = self.prev         # only at the first drop
            self.second = root                 # at every drop
        self.prev = root
        self.inorder(root.right)

7Code line by line

8Dry run on Example B (the teacher's second tree)

        6
      /   \
     8     3
    / \   / \
   1   4 7   10

1. inorder(6) → inorder(8) → inorder(1) → its left is None, return. Visit 1: prev is None → no check. prev = 1. Its right is None.
2. Back to 8. Visit 8: prev 1 > 8? no. prev = 8.
3. Go to 8's right, 4. Visit 4: prev 8 > 4? yes, drop 1. first is None → first = 8. second = 4. prev = 4.
4. Back up to 6. Visit 6: prev 4 > 6? no. prev = 6.
5. Go right to 3, then left to 7. Visit 7: 6 > 7? no. prev = 7.
6. Back to 3. Visit 3: prev 7 > 3? yes, drop 2. first is already 8 → don't touch it. second = 3 (replaces 4). prev = 3.
7. Go right to 10. Visit 10: 3 > 10? no. prev = 10. The walk ends.
8. Swap first (8) and second (3): the left child of 6 becomes 3 and the right child becomes 8 ✓. Inorder is now 1 3 4 6 7 8 10.

Quick check on LeetCode Example 1 (root 1, left 3, 3's right 2): inorder 3 2 1. Visit 2: 3 > 2, drop → first = 3, second = 2. Visit 1: 2 > 1, drop → second = 1. Swap 3 and 1 ✓. Another far-apart case with two drops.

9Complexity & remember

• Time O(n): one inorder walk, O(1) work per node, plus an O(1) swap at the end. Only one pass now, instead of three.
• Space O(h): no list, just the recursion stack, as tall as the tree. That's about log n for a balanced BST and n for a skewed (chain-shaped) one.

(LeetCode also asks, as a follow-up, for O(1) space. That needs Morris traversal, which the teacher doesn't cover in this video.)

Part D · Revision page

def inorder_list(r):
    return [] if r is None else inorder_list(r.left) + [r.val] + inorder_list(r.right)

a = TreeNode(3, TreeNode(1), TreeNode(4, TreeNode(2)))
b = TreeNode(6, TreeNode(8, TreeNode(1), TreeNode(4)),
                TreeNode(3, TreeNode(7), TreeNode(10)))
c = TreeNode(1, TreeNode(3, None, TreeNode(2)))

for t in (a, b, c):
    Solution().recoverTree(t)
    print(inorder_list(t))
# [1, 2, 3, 4]
# [1, 3, 4, 6, 7, 8, 10]
# [1, 2, 3]

Based on this video: Recover Binary Search Tree