LeetCode 99 - Recover Binary Search Tree

The problem gives us the root of a binary search tree, but exactly two nodes in the tree have had their values swapped accidentally. Our task is to restore the tree so that it once again satisfies the binary search tree property, without modifying the tree structure itself.

leetcodemediumtreedepth-first-searchbinary-search-treebinary-tree

LeetCode Problem 99

Difficulty: 🟡 Medium
Topics: Tree, Depth-First Search, Binary Search Tree, Binary Tree

Solution

Problem Understanding

The problem gives us the root of a binary search tree, but exactly two nodes in the tree have had their values swapped accidentally. Our task is to restore the tree so that it once again satisfies the binary search tree property, without modifying the tree structure itself.

A binary search tree, or BST, has a very important property:

  • Every node in the left subtree contains a value smaller than the current node.
  • Every node in the right subtree contains a value larger than the current node.

One of the most useful consequences of this property is that an inorder traversal of a valid BST produces values in strictly increasing order.

The input is the root node of the corrupted BST. The output is not returned directly. Instead, we must modify the tree in place by swapping the incorrect values back to their proper locations.

The constraints tell us that the tree contains between 2 and 1000 nodes. This is small enough that even an O(n) traversal is completely acceptable. However, the follow up asks whether we can solve the problem using constant extra space, which hints that the intended optimal solution avoids storing the entire traversal.

There are several important edge cases to keep in mind:

  • The swapped nodes may be adjacent in inorder traversal.
  • The swapped nodes may be far apart in inorder traversal.
  • One swapped node may be the root.
  • The tree may contain only two nodes.
  • The BST property is guaranteed to be violated by exactly two swapped nodes, so we do not need to handle arbitrary corruption.

A naive implementation can fail when the swapped nodes are not adjacent, because there may be two inversion points instead of one. Correct handling requires carefully identifying both misplaced nodes.

Approaches

Brute Force Approach

The most straightforward solution is to perform an inorder traversal of the tree and store all nodes in an array.

Since inorder traversal of a valid BST should produce sorted values, we can compare the collected sequence with a sorted version of itself. The two nodes whose values differ are the swapped nodes. Once identified, we swap their values back.

This approach works because sorting reveals the correct order of values, and only two positions are incorrect.

However, this solution requires additional memory proportional to the number of nodes because we store the traversal. While acceptable for the given constraints, it does not satisfy the follow up requirement asking for constant extra space.

Optimal Approach

The key observation is that inorder traversal of a BST must be sorted.

If exactly two nodes are swapped, the inorder sequence will contain one or two inversions.

For example:

Correct inorder:
1 2 3 4 5

Swapped inorder:
1 4 3 2 5

Here:

  • 4 > 3 is an inversion
  • 3 > 2 is another inversion

The first misplaced node is the larger value from the first inversion.

The second misplaced node is the smaller value from the last inversion.

We can detect these inversions during inorder traversal without storing the entire traversal. We only need:

  • prev, the previously visited node
  • first, the first incorrect node
  • second, the second incorrect node

After traversal completes, swapping first.val and second.val restores the BST.

Approach Time Complexity Space Complexity Notes
Brute Force O(n log n) O(n) Store inorder traversal and compare with sorted array
Optimal O(n) O(h) Detect inversions during inorder traversal, where h is tree height

The recursive solution uses O(h) stack space due to recursion. A Morris Traversal version can achieve true O(1) auxiliary space.

Algorithm Walkthrough

  1. Perform an inorder traversal of the tree.

Inorder traversal visits nodes in the order:

left -> root -> right

For a valid BST, this produces a sorted sequence. 2. Keep track of the previously visited node.

During traversal, store a pointer called prev.

If the BST is valid, we should always have:

prev.val < current.val
  1. Detect inversions.

If we encounter:

prev.val > current.val

then the BST ordering is violated. 4. Record the first misplaced node.

The first time an inversion appears:

  • first = prev
  • second = current

The larger node from the inversion is definitely misplaced. 5. Update the second misplaced node if another inversion occurs.

If another inversion appears later:

  • update second = current

This handles the case where swapped nodes are not adjacent. 6. Continue traversal until all nodes are processed.

We must traverse the entire tree because the second incorrect node may appear later. 7. Swap the values of the two misplaced nodes.

After traversal finishes:

first.val, second.val = second.val, first.val

This restores BST ordering.

Why it works

A valid BST produces a strictly increasing inorder sequence. Swapping two values introduces ordering violations. If the swapped nodes are adjacent, there will be one inversion. If they are separated, there will be two inversions.

The first incorrect node is always the larger value from the first inversion. The second incorrect node is always the smaller value from the last inversion. Swapping these two values restores the sorted inorder order, which restores the BST property.

Python Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from typing import Optional

class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        first = None
        second = None
        prev = None

        def inorder(node: Optional[TreeNode]) -> None:
            nonlocal first, second, prev

            if not node:
                return

            inorder(node.left)

            if prev and prev.val > node.val:
                if first is None:
                    first = prev
                second = node

            prev = node

            inorder(node.right)

        inorder(root)

        if first and second:
            first.val, second.val = second.val, first.val

The implementation follows the inorder traversal strategy discussed earlier.

The variables first and second store the two misplaced nodes. The variable prev keeps track of the previously visited node during traversal.

The recursive inorder function traverses the tree in sorted order. At each node, we compare the current node's value with the previous node's value.

If prev.val > node.val, we have detected an inversion.

During the first inversion:

first = prev
second = node

If another inversion appears later, only second is updated.

After traversal completes, the two incorrect values are swapped back.

This solution modifies the tree directly and does not create a new tree.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func recoverTree(root *TreeNode) {
    var first *TreeNode
    var second *TreeNode
    var prev *TreeNode

    var inorder func(node *TreeNode)

    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        inorder(node.Left)

        if prev != nil && prev.Val > node.Val {
            if first == nil {
                first = prev
            }
            second = node
        }

        prev = node

        inorder(node.Right)
    }

    inorder(root)

    if first != nil && second != nil {
        first.Val, second.Val = second.Val, first.Val
    }
}

The Go implementation is structurally very similar to the Python version.

Since Go does not support nested functions with nonlocal, we use closure variables directly inside the recursive function.

Go uses nil instead of Python's None for null references.

Pointers are used naturally because tree nodes are referenced through *TreeNode.

Worked Examples

Example 1

Input:
    1
   /
  3
   \
    2

Inorder traversal produces:

3, 2, 1

This is not sorted.

Current Node Prev Node Inversion? First Second
3 None No None None
2 3 Yes 3 2
1 2 Yes 3 1

After traversal:

first = 3
second = 1

Swap values:

1 <-> 3

Result:

    3
   /
  1
   \
    2

Example 2

Input:
    3
   / \
  1   4
     /
    2

Inorder traversal:

1, 3, 2, 4

Violation occurs because 3 > 2.

Current Node Prev Node Inversion? First Second
1 None No None None
3 1 No None None
2 3 Yes 3 2
4 2 No 3 2

Swap:

3 <-> 2

Correct BST:

    2
   / \
  1   4
     /
    3

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once
Space O(h) Recursive call stack uses height of tree

The traversal processes each node exactly one time, giving linear time complexity.

The recursive implementation uses stack space proportional to the tree height. In the worst case of a completely skewed tree, this becomes O(n). In a balanced tree, it is O(log n).

A Morris Traversal implementation can reduce auxiliary space to true O(1).

Test Cases

# Helper functions for testing

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

def inorder(root):
    if not root:
        return []
    return inorder(root.left) + [root.val] + inorder(root.right)

# Test 1: Example 1
root = TreeNode(1)
root.left = TreeNode(3)
root.left.right = TreeNode(2)

Solution().recoverTree(root)

assert inorder(root) == [1, 2, 3]  # adjacent violations

# Test 2: Example 2
root = TreeNode(3)
root.left = TreeNode(1)
root.right = TreeNode(4)
root.right.left = TreeNode(2)

Solution().recoverTree(root)

assert inorder(root) == [1, 2, 3, 4]  # non-adjacent swap

# Test 3: Two-node tree
root = TreeNode(2)
root.left = TreeNode(1)

root.val, root.left.val = root.left.val, root.val

Solution().recoverTree(root)

assert inorder(root) == [1, 2]  # minimum tree size

# Test 4: Root involved in swap
root = TreeNode(2)
root.left = TreeNode(3)
root.right = TreeNode(1)

Solution().recoverTree(root)

assert inorder(root) == [1, 2, 3]  # root swapped

# Test 5: Large skewed tree
root = TreeNode(1)
root.right = TreeNode(3)
root.right.left = TreeNode(2)

Solution().recoverTree(root)

assert inorder(root) == [1, 2, 3]  # skewed structure

# Test 6: Adjacent inorder swap
root = TreeNode(3)
root.left = TreeNode(2)
root.right = TreeNode(4)
root.left.left = TreeNode(1)

root.val, root.left.val = root.left.val, root.val

Solution().recoverTree(root)

assert inorder(root) == [1, 2, 3, 4]  # adjacent swapped nodes

# Test 7: Non-adjacent inorder swap
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(5)
root.right.left = TreeNode(3)
root.right.right = TreeNode(7)

Solution().recoverTree(root)

assert inorder(root) == [1, 2, 3, 4, 5, 6, 7]  # distant swapped nodes
Test Why
Example 1 Verifies handling of two inversions
Example 2 Verifies non-adjacent swapped nodes
Two-node tree Smallest valid input size
Root involved in swap Ensures root corruption is handled
Large skewed tree Tests unbalanced tree behavior
Adjacent inorder swap Verifies single inversion handling
Non-adjacent inorder swap Verifies double inversion handling

Edge Cases

Adjacent Swapped Nodes

If the swapped nodes are adjacent in inorder traversal, there will only be one inversion instead of two.

For example:

1 3 2 4

A buggy implementation may expect two violations and fail to identify the correct nodes.

This implementation handles the case correctly because the first inversion already identifies both misplaced nodes.

Non-Adjacent Swapped Nodes

If the swapped nodes are far apart, there will be two inversions.

For example:

1 5 3 4 2 6

The correct nodes are 5 and 2.

A naive implementation might incorrectly swap 5 and 3, because it only examines the first inversion.

This implementation updates second every time an inversion is found, ensuring the final incorrect node is captured properly.

Root Node Is Swapped

Sometimes one of the swapped nodes is the root.

Since inorder traversal processes nodes purely by ordering and not by position, the algorithm does not care whether a node is the root, leaf, or internal node.

The comparison logic works uniformly across the entire tree, so root corruption is naturally handled without any special cases.