This problem requires detecting two nodes in a BST that were swapped and restoring the tree without changing its structure. Using in-order traversal, you can track violations where a previous node is greater than the current node. Once identified, swapping the correct nodes restores BST validity while preserving tree shape, ensuring all left and right child relationships remain valid.
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.
How GhostInterview Helps
- Capture the BST input visually and map node positions to track violations quickly.
- Guide the answer path by identifying in-order inversions and explain time and space complexities for each approach.
- Support screen-share workflows by highlighting nodes on traversal layers and showing live swaps to restore BST structure.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
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.
Need direct help with Recover Binary Search Tree instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Recover Binary Search Tree from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Validate Binary Search Tree problem checks if a binary tree satisfies BST properties using tree traversal and state tracking.
Open problem page#230 Kth Smallest Element in a BSTFind the kth smallest element in a BST by leveraging in-order traversal to efficiently track node order and count.
Open problem page#235 Lowest Common Ancestor of a Binary Search TreeFind the lowest common ancestor (LCA) of two nodes in a binary search tree, using binary-tree traversal and state tracking.
Open problem page