#99

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Recover Binary Search Tree

Recover a BST where two nodes are swapped by mistake using in-order traversal and careful state tracking to restore correct structure efficiently.

tree depth first search binary search tree binary tree

Problem Statement

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 BST so that it satisfies the standard property where the left child is less than the node and the right child is greater, without altering the tree's structure or creating new nodes.

For example, given root = [1,3,null,null,2], the correct BST after recovery should be [3,1,null,null,2], because 3 and 1 were swapped. Similarly, for root = [3,1,4,null,null,2], swapping 2 and 3 restores the BST. You must handle trees with 2 to 1000 nodes and node values in the range [-2^31, 2^31-1], ensuring the traversal correctly identifies misplaced nodes.

Examples

Example 1

Input: root = [1,3,null,null,2]

Output: [3,1,null,null,2]

3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

Example 2

Input: root = [3,1,4,null,null,2]

Output: [2,1,4,null,null,3]

2 cannot be in the right subtree of 3 because 2 < 3. Swapping 2 and 3 makes the BST valid.

Constraints

The number of nodes in the tree is in the range [2, 1000].
-231 <= Node.val <= 231 - 1

Solution Approach

In-Order Traversal with Pointers

Perform an in-order DFS traversal to process nodes in ascending order. Maintain pointers to the previous node and the two nodes that are out of order. When a previous node has a value greater than the current node, mark the nodes as candidates for swapping. At the end of traversal, swap the two identified nodes to restore the BST. This approach relies on the property that in-order traversal of a valid BST produces a sorted sequence, making violations easy to detect.

Recursive State Tracking

Use recursion to traverse the BST while keeping track of the previous node in the sequence. Compare each current node with the previous to detect inversion points. Record the first and second nodes involved in any violation. The recursion ensures the full tree is visited without extra data structures beyond pointers. This method is efficient and naturally leverages the tree’s structure while focusing on the problem’s failure mode of swapped nodes, allowing direct correction after traversal.

Iterative Traversal with Stack

Implement an iterative in-order traversal using an explicit stack to avoid recursion. Push nodes onto the stack while traversing left children, then process nodes in order. Keep track of the previous node and identify two nodes where the BST property is violated. After completing traversal, swap the values of the two problematic nodes. This approach avoids recursion depth issues and still strictly follows the binary-tree traversal and state-tracking pattern needed for this specific BST recovery problem.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) since each node is visited once during traversal, and the space complexity is O(h), where h is the height of the tree, due to recursion stack or explicit stack storage, making the provided complexities align with in-order DFS or iterative traversal strategies.

What Interviewers Usually Probe

Do you identify the two swapped nodes in a single traversal?
Can you restore the BST without creating new nodes or changing its structure?
Will you handle edge cases where swapped nodes are adjacent in in-order sequence?

Common Pitfalls or Variants

Common pitfalls

Failing to track the previous node correctly, causing missed inversion points.
Swapping incorrect nodes when the swapped nodes are not adjacent, producing an invalid BST.
Using extra storage like a full array of node values instead of pointers, increasing space unnecessarily.

Follow-up variants

Recover BST when multiple pairs of nodes are swapped.
Recover BST using Morris Traversal to achieve O(1) space.
Recover a BST where only leaf nodes may be swapped, requiring subtree checks.

FAQ

How do I detect which two nodes were swapped in a BST?

Perform an in-order traversal and compare each node with its previous node. Nodes causing the violation are marked as candidates for swapping, and swapping them restores BST validity.

Can I recover the BST without recursion?

Yes, using an iterative in-order traversal with a stack allows you to track previous nodes and detect swapped nodes without recursion while maintaining O(h) space complexity.

What happens if the swapped nodes are adjacent in the in-order sequence?

Even if the nodes are adjacent, the same in-order comparison identifies the inversion, allowing a single swap between the two nodes to restore the BST correctly.

Does this approach handle all tree sizes in constraints?

Yes, the method works for trees from 2 to 1000 nodes, efficiently visiting each node once and using space proportional to tree height, so it handles balanced and skewed trees.

Why is in-order traversal critical for Recover Binary Search Tree?

In-order traversal produces nodes in ascending order for a valid BST. Comparing sequential nodes directly exposes violations, making it the most direct way to detect and recover swapped nodes.

terminal

Solution

Solution 1: In-order Traversal

In-order traversal of a binary search tree results in an increasing sequence. If two nodes' values are mistakenly swapped, there will definitely be two reverse pairs in the sequence obtained from the in-order traversal. We use `first` and `second` to record the smaller and larger values of these two reverse pairs, respectively. Finally, swapping the values of these two nodes will correct the mistake.

# 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
class Solution:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        def dfs(root):
            if root is None:
                return
            nonlocal prev, first, second
            dfs(root.left)
            if prev and prev.val > root.val:
                if first is None:
                    first = prev
                second = root
            prev = root
            dfs(root.right)

        prev = first = second = None
        dfs(root)
        first.val, second.val = second.val, first.val

Continue Practicing

#98 validate binary search tree #230 kth smallest element in a bst #235 lowest common ancestor of a binary search tree