Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

99. Recover Binary Search Tree - Leetcode Solution

Code Implementation

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

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        first = second = prev = None
        stack = []
        curr = root

        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            if prev and prev.val > curr.val:
                if not first:
                    first = prev
                second = curr
            prev = curr
            curr = curr.right

        if first and second:
            first.val, second.val = second.val, first.val
      
// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;
        std::stack<TreeNode*> stack;
        TreeNode* curr = root;

        while (!stack.empty() || curr) {
            while (curr) {
                stack.push(curr);
                curr = curr->left;
            }
            curr = stack.top();
            stack.pop();
            if (prev && prev->val > curr->val) {
                if (!first) first = prev;
                second = curr;
            }
            prev = curr;
            curr = curr->right;
        }

        if (first && second) {
            std::swap(first->val, second->val);
        }
    }
};
      
// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode first = null, second = null, prev = null;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode curr = root;

        while (!stack.isEmpty() || curr != null) {
            while (curr != null) {
                stack.push(curr);
                curr = curr.left;
            }
            curr = stack.pop();
            if (prev != null && prev.val > curr.val) {
                if (first == null) first = prev;
                second = curr;
            }
            prev = curr;
            curr = curr.right;
        }

        if (first != null && second != null) {
            int tmp = first.val;
            first.val = second.val;
            second.val = tmp;
        }
    }
}
      
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {void} Do not return anything, modify root in-place instead.
 */
var recoverTree = function(root) {
    let first = null, second = null, prev = null;
    let stack = [];
    let curr = root;

    while (stack.length || curr) {
        while (curr) {
            stack.push(curr);
            curr = curr.left;
        }
        curr = stack.pop();
        if (prev && prev.val > curr.val) {
            if (!first) first = prev;
            second = curr;
        }
        prev = curr;
        curr = curr.right;
    }
    if (first && second) {
        let tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
};

Problem Description

You are given the root of a binary search tree (BST) in which exactly two nodes have had their values swapped by mistake. Your task is to recover the tree without changing its structure, by swapping the values of the two incorrect nodes back to their original positions.

Key constraints:
  • There is exactly one valid solution.
  • You must not change the tree structure, only the node values.
  • Do not create new nodes or use extra space for a list of nodes (O(1) or O(h) space, where h is the height of the tree, is acceptable for recursion/stack).
  • Input is provided as a TreeNode root.

Thought Process

The problem asks us to fix a BST where two nodes have been swapped. In a correct BST, an in-order traversal yields a sorted sequence. So, if two nodes are swapped, the in-order sequence will show two places where the order is violated.

A brute-force idea is to collect all node values, sort them, and reassign, but this uses extra space and doesn't leverage BST properties.

Instead, we should look for the two nodes that are out of order during in-order traversal. By tracking the previous node visited, we can spot the two places where the BST property is violated, and then swap those nodes' values to fix the tree.

Solution Approach

To efficiently recover the BST, follow these steps:
  1. In-order Traversal: Traverse the tree in-order (left, root, right). In a correct BST, the values should be in increasing order.
  2. Detect Swapped Nodes: Keep track of the previous node visited (prev). If prev.val > current.val, it's a violation.
    There are two scenarios:
    • If the swapped nodes are adjacent, you'll see only one violation.
    • If they're not adjacent, you'll see two violations.
    In both cases, you need to remember the first and second nodes involved in the violation.
  3. Swap Values: After traversal, swap the values of the two nodes you identified.
  4. Why use a stack? We use an explicit stack to perform iterative in-order traversal, which is O(h) space, where h is the height of the tree.
Key design choices:
  • Iterative in-order traversal avoids recursion stack overflow.
  • Track prev, first, and second nodes to identify the swapped nodes.
  • Swapping values is enough; no need to alter pointers or tree structure.

Example Walkthrough

Example Input:
Suppose the BST should be 1 - 2 - 3 (in-order), but nodes 2 and 3 are swapped:
      3
     / \
    1   4
       /
      2
Step-by-step traversal:
  1. Visit 1 (prev = None). No violation.
  2. Visit 3 (prev = 1). 1 < 3, OK.
  3. Visit 4 (prev = 3). 3 < 4, OK.
  4. Visit 2 (prev = 4). 4 > 2, violation detected! Mark first = 4, second = 2.
After traversal, swap values of 4 and 2. The corrected BST in-order is 1, 2, 3, 4.
Why does this work? Because the in-order property of BSTs uniquely identifies the misplaced nodes.

Time and Space Complexity

Brute-force approach:
  • Time: O(N) to traverse and collect all nodes, O(N log N) to sort, O(N) to reassign values. Total: O(N log N).
  • Space: O(N) for storing the node values.
Optimized approach (in-order traversal):
  • Time: O(N), as each node is visited once.
  • Space: O(h), where h is the height of the tree (stack space for traversal).
The optimized approach is both faster and uses less space, leveraging the BST property.

Summary

The solution exploits the BST's in-order property to identify the two swapped nodes by finding violations in the order during traversal. By tracking the previous node and the first/second violations, we can restore the BST with a simple value swap. This approach is efficient, elegant, and leverages the structure of the BST without requiring extra memory for storing all nodes or values.