Facebook Pixel

99. Recover Binary Search Tree

Problem Description

You have a binary search tree (BST) where exactly two nodes have had their values swapped by mistake. Your task is to fix the tree by identifying these two incorrectly placed nodes and swapping their values back to restore the valid BST property.

The key requirements are:

  • The tree structure (connections between nodes) must remain unchanged
  • You can only modify the values of nodes, not move nodes around
  • Exactly two nodes have incorrect values that need to be swapped

For example, if you have a BST that should be [1, 2, 3, 4, 5] in in-order traversal, but two nodes were swapped resulting in [1, 4, 3, 2, 5], you need to identify that nodes with values 4 and 2 are in the wrong positions and swap them back.

The solution uses in-order traversal to detect anomalies. In a valid BST, in-order traversal produces values in ascending order. When two nodes are swapped, this creates violations of the ascending order - these violations help identify which two nodes need to be swapped back.

The algorithm tracks:

  • prev: The previously visited node during in-order traversal
  • first: The first node that appears out of order (will be the larger value in the first violation)
  • second: The second node that appears out of order (will be the smaller value in the last violation)

During traversal, whenever prev.val > root.val is detected (a violation of BST property), the algorithm records the nodes involved. After traversal completes, swapping the values of first and second restores the tree to its correct state.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

  • Yes: A binary search tree is a special type of graph where each node has at most two children (left and right). Trees are a subset of graphs with no cycles and a hierarchical structure.

Is it a tree?

  • Yes: The problem explicitly states we're working with a binary search tree (BST). A BST is a tree data structure where each node follows the property that all values in the left subtree are less than the node's value, and all values in the right subtree are greater.

DFS

  • Yes: We arrive at DFS (Depth-First Search) as our algorithm choice.

Conclusion: The flowchart suggests using DFS for this problem. This makes perfect sense because:

  1. We need to traverse the entire tree to identify the two swapped nodes
  2. In-order DFS traversal of a BST naturally gives us values in sorted order
  3. DFS allows us to visit each node exactly once while maintaining the context of previously visited nodes (using the prev variable)
  4. The recursive nature of DFS perfectly matches the recursive structure of the tree

The DFS approach in the solution performs an in-order traversal (left → root → right), which is ideal for BST problems since it processes nodes in their sorted order, making it easy to detect when two nodes violate the BST property due to being swapped.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

Think about what happens when you perform an in-order traversal on a valid BST - you get all values in ascending order, like [1, 2, 3, 4, 5]. This is the key insight that unlocks the solution.

Now, if exactly two nodes are swapped, this ascending sequence gets disrupted. For instance, if nodes with values 2 and 4 are swapped, the in-order traversal gives us [1, 4, 3, 2, 5]. Notice something interesting? There are violations where a larger value appears before a smaller one:

  • 4 > 3 (first violation)
  • 3 > 2 (second violation)

These violations are our clues! The swapped nodes must be involved in these violations.

Consider two scenarios:

Scenario 1: Adjacent nodes are swapped If we swap adjacent elements like 3 and 4 in [1, 2, 3, 4, 5], we get [1, 2, 4, 3, 5]. There's only one violation: 4 > 3. The two nodes involved in this single violation are the ones we need to swap back.

Scenario 2: Non-adjacent nodes are swapped If we swap non-adjacent elements like 2 and 5 in [1, 2, 3, 4, 5], we get [1, 5, 3, 4, 2]. Now we have two violations:

  • 5 > 3 (first violation)
  • 4 > 2 (second violation)

Here's the pattern: The first incorrectly placed node appears in the first violation (it's the larger value that shouldn't be there yet), and the second incorrectly placed node appears in the last violation (it's the smaller value that should have appeared earlier).

So our strategy becomes:

  1. Do an in-order DFS traversal while keeping track of the previous node
  2. Whenever we find prev.val > current.val, we've found a violation
  3. The first time we see a violation, mark the prev node as our first swapped node
  4. Keep updating the second node to be the current node whenever we see a violation
  5. After traversal, swap the values of first and second

This works because in the case of adjacent swaps, both first and second get set in the same violation. In the case of non-adjacent swaps, first gets set in the first violation and second gets updated in the last violation.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Solution Approach

The implementation uses an in-order DFS traversal to detect and fix the swapped nodes. Let's walk through the key components:

Core Data Structures:

  • Three pointers are maintained: prev, first, and second
    • prev: Tracks the previously visited node during traversal
    • first: Stores the first node that appears out of order
    • second: Stores the second node that appears out of order

The DFS Traversal Pattern:

def dfs(root):
    if root is None:
        return
    dfs(root.left)    # Visit left subtree
    # Process current node
    dfs(root.right)   # Visit right subtree

This is the standard in-order traversal template that processes nodes in sorted order for a BST.

Detection Logic: During the traversal, after visiting the left subtree but before visiting the right subtree, we check:

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

This condition prev.val > root.val identifies a violation of the BST property. When found:

  • If it's the first violation (first is None), we mark prev as the first node
  • We always update second to be the current node (root)

The reason for always updating second is crucial:

  • If nodes are adjacent, both get set in the same violation
  • If nodes are non-adjacent, second gets overwritten in the second violation with the correct node

State Update: After processing the current node's value, we update prev to point to the current node:

prev = root

This ensures that when we move to the next node in the traversal, we have the correct previous node for comparison.

The Final Swap: After the complete traversal:

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

This single line swaps the values of the two identified nodes, restoring the BST property.

Why This Works: The algorithm leverages the fact that in-order traversal of a BST should produce a sorted sequence. Any deviation from this sorted order indicates the presence of swapped nodes. By carefully tracking violations and the nodes involved, we can identify exactly which two nodes need their values exchanged to restore the tree's validity.

The beauty of this approach is that it requires only O(1) extra space (excluding the recursion stack) and O(n) time complexity, visiting each node exactly once.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to see how the algorithm identifies and fixes swapped nodes.

Initial BST (with swapped nodes):

      3
     / \
    1   4
       / \
      2   5

The values 2 and 3 have been swapped. The correct BST should have 2 at the root and 3 where 2 currently is.

Step-by-step traversal:

Let's trace through the in-order traversal with our three pointers: prev = None, first = None, second = None

  1. Visit node 1

    • Left subtree is None, process current node
    • Check: prev is None, so no comparison
    • Update: prev = node(1)
    • Right subtree is None
  2. Visit node 3 (root)

    • Left subtree already visited
    • Check: prev.val (1) > root.val (3)? No, so no violation
    • Update: prev = node(3)
    • Move to right subtree
  3. Visit node 2

    • Left subtree is None
    • Check: prev.val (3) > root.val (2)? Yes! First violation found
    • Since first is None, set first = prev (node with value 3)
    • Set second = root (node with value 2)
    • Update: prev = node(2)
    • Right subtree is None
  4. Visit node 4

    • Left subtree already visited
    • Check: prev.val (2) > root.val (4)? No, so no violation
    • Update: prev = node(4)
    • Move to right subtree
  5. Visit node 5

    • Left subtree is None
    • Check: prev.val (4) > root.val (5)? No, so no violation
    • Update: prev = node(5)
    • Right subtree is None

After traversal:

  • first points to the node with value 3
  • second points to the node with value 2
  • We swap their values: first.val = 2, second.val = 3

Final corrected BST:

      2
     / \
    1   4
       / \
      3   5

The in-order traversal now correctly produces [1, 2, 3, 4, 5], confirming our BST is restored!

Key insight: The algorithm detected that when we encountered value 2 after value 3, something was wrong. Since these were the only two nodes involved in a violation, they must be the swapped pair. By exchanging their values, we restored the proper BST ordering.

Solution Implementation

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7
8from typing import Optional
9
10class Solution:
11    def recoverTree(self, root: Optional[TreeNode]) -> None:
12        """
13        Do not return anything, modify root in-place instead.
14      
15        This function recovers a BST where exactly two nodes have been swapped.
16        Uses Morris Traversal concept with in-order traversal to find the two swapped nodes.
17        """
18      
19        def inorder_traversal(node: Optional[TreeNode]) -> None:
20            """
21            Perform in-order traversal to find two swapped nodes in BST.
22          
23            In a valid BST's in-order traversal, values should be in ascending order.
24            We look for violations of this property to identify swapped nodes.
25            """
26            if node is None:
27                return
28          
29            nonlocal previous_node, first_swapped, second_swapped
30          
31            # Traverse left subtree
32            inorder_traversal(node.left)
33          
34            # Process current node
35            # Check if current node violates BST property (previous > current)
36            if previous_node and previous_node.val > node.val:
37                if first_swapped is None:
38                    # First violation found: mark the previous node as first swapped
39                    first_swapped = previous_node
40                # Always update second swapped to current node
41                # This handles both adjacent and non-adjacent swaps
42                second_swapped = node
43          
44            # Update previous node for next comparison
45            previous_node = node
46          
47            # Traverse right subtree
48            inorder_traversal(node.right)
49      
50        # Initialize tracking variables
51        previous_node = None      # Tracks the previous node in in-order traversal
52        first_swapped = None      # First node that violates BST property
53        second_swapped = None     # Second node that violates BST property
54      
55        # Find the two swapped nodes
56        inorder_traversal(root)
57      
58        # Swap the values of the two identified nodes to recover the BST
59        first_swapped.val, second_swapped.val = second_swapped.val, first_swapped.val
60
1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 *     int val;
5 *     TreeNode left;
6 *     TreeNode right;
7 *     TreeNode() {}
8 *     TreeNode(int val) { this.val = val; }
9 *     TreeNode(int val, TreeNode left, TreeNode right) {
10 *         this.val = val;
11 *         this.left = left;
12 *         this.right = right;
13 *     }
14 * }
15 */
16class Solution {
17    // Previous node visited during in-order traversal
18    private TreeNode previousNode;
19  
20    // First swapped node (larger value in wrong position)
21    private TreeNode firstSwappedNode;
22  
23    // Second swapped node (smaller value in wrong position)
24    private TreeNode secondSwappedNode;
25
26    /**
27     * Recovers a binary search tree where exactly two nodes have been swapped by mistake.
28     * The recovery is done by swapping back the values of the two incorrect nodes.
29     * 
30     * @param root The root of the binary search tree to recover
31     */
32    public void recoverTree(TreeNode root) {
33        // Perform in-order traversal to identify the two swapped nodes
34        inOrderTraversal(root);
35      
36        // Swap the values of the two identified nodes to recover the BST
37        int temp = firstSwappedNode.val;
38        firstSwappedNode.val = secondSwappedNode.val;
39        secondSwappedNode.val = temp;
40    }
41
42    /**
43     * Performs an in-order traversal of the tree to identify nodes that violate BST property.
44     * In a valid BST, in-order traversal yields values in ascending order.
45     * When two nodes are swapped, there will be one or two violations of this order.
46     * 
47     * @param currentNode The current node being visited in the traversal
48     */
49    private void inOrderTraversal(TreeNode currentNode) {
50        // Base case: if current node is null, return
51        if (currentNode == null) {
52            return;
53        }
54      
55        // Recursively traverse the left subtree
56        inOrderTraversal(currentNode.left);
57      
58        // Process current node: check for BST violation
59        if (previousNode != null && previousNode.val > currentNode.val) {
60            // Found a violation where previous value is greater than current value
61          
62            // If this is the first violation found, mark the previous node as first swapped node
63            if (firstSwappedNode == null) {
64                firstSwappedNode = previousNode;
65            }
66          
67            // Always update the second swapped node to current node
68            // This handles both adjacent and non-adjacent swapped nodes
69            secondSwappedNode = currentNode;
70        }
71      
72        // Update previous node for next comparison
73        previousNode = currentNode;
74      
75        // Recursively traverse the right subtree
76        inOrderTraversal(currentNode.right);
77    }
78}
79
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 *     int val;
5 *     TreeNode *left;
6 *     TreeNode *right;
7 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14    void recoverTree(TreeNode* root) {
15        // Previous node during in-order traversal
16        TreeNode* previousNode = nullptr;
17      
18        // First misplaced node (larger value in wrong position)
19        TreeNode* firstMisplacedNode = nullptr;
20      
21        // Second misplaced node (smaller value in wrong position)
22        TreeNode* secondMisplacedNode = nullptr;
23      
24        // Lambda function for in-order traversal to find swapped nodes
25        function<void(TreeNode*)> inorderTraversal = [&](TreeNode* currentNode) {
26            // Base case: return if node is null
27            if (!currentNode) {
28                return;
29            }
30          
31            // Traverse left subtree
32            inorderTraversal(currentNode->left);
33          
34            // Process current node
35            // Check if previous node's value is greater than current node's value
36            // This violates BST property
37            if (previousNode && previousNode->val > currentNode->val) {
38                // First violation: mark the previous node as first misplaced
39                if (!firstMisplacedNode) {
40                    firstMisplacedNode = previousNode;
41                }
42                // Always update second misplaced node to current node
43                // This handles both adjacent and non-adjacent swapped nodes
44                secondMisplacedNode = currentNode;
45            }
46          
47            // Update previous node for next comparison
48            previousNode = currentNode;
49          
50            // Traverse right subtree
51            inorderTraversal(currentNode->right);
52        };
53      
54        // Perform in-order traversal to identify the two swapped nodes
55        inorderTraversal(root);
56      
57        // Swap the values of the two misplaced nodes to recover the BST
58        swap(firstMisplacedNode->val, secondMisplacedNode->val);
59    }
60};
61
1/**
2 * Definition for a binary tree node.
3 */
4interface TreeNode {
5    val: number;
6    left: TreeNode | null;
7    right: TreeNode | null;
8}
9
10/**
11 * Recovers a binary search tree where exactly two nodes were swapped by mistake.
12 * Uses in-order traversal to find the two swapped nodes and then swaps their values.
13 * @param root - The root of the binary search tree to recover
14 * @return void - Modifies the tree in-place
15 */
16function recoverTree(root: TreeNode | null): void {
17    // Track the previous node during in-order traversal
18    let previousNode: TreeNode | null = null;
19    // First node that violates BST property (larger node in the first violation)
20    let firstSwappedNode: TreeNode | null = null;
21    // Second node that violates BST property (smaller node in the last violation)
22    let secondSwappedNode: TreeNode | null = null;
23  
24    /**
25     * Performs in-order traversal to identify the two swapped nodes.
26     * In a valid BST, in-order traversal yields values in ascending order.
27     * We look for violations where previous value > current value.
28     * @param currentNode - The current node being visited
29     */
30    function inOrderTraversal(currentNode: TreeNode | null): void {
31        if (!currentNode) {
32            return;
33        }
34      
35        // Traverse left subtree
36        inOrderTraversal(currentNode.left);
37      
38        // Process current node - check for BST violation
39        if (previousNode && previousNode.val > currentNode.val) {
40            // First violation: mark the previous node as first swapped node
41            if (!firstSwappedNode) {
42                firstSwappedNode = previousNode;
43            }
44            // Always update second swapped node (handles both adjacent and non-adjacent swaps)
45            secondSwappedNode = currentNode;
46        }
47      
48        // Update previous node for next comparison
49        previousNode = currentNode;
50      
51        // Traverse right subtree
52        inOrderTraversal(currentNode.right);
53    }
54  
55    // Find the two swapped nodes
56    inOrderTraversal(root);
57  
58    // Swap the values of the two identified nodes to recover the BST
59    if (firstSwappedNode && secondSwappedNode) {
60        const tempValue: number = firstSwappedNode.val;
61        firstSwappedNode.val = secondSwappedNode.val;
62        secondSwappedNode.val = tempValue;
63    }
64}
65

Time and Space Complexity

The time complexity is O(n), where n is the number of nodes in the binary search tree. This is because the algorithm performs an in-order traversal of the tree using DFS, visiting each node exactly once. During the traversal, each node is processed with constant time operations (comparisons and assignments), resulting in linear time complexity overall.

The space complexity is O(n) in the worst case. While the algorithm uses only O(1) extra space for the variables prev, first, and second, the recursive DFS traversal uses the call stack. In the worst case, when the tree is completely unbalanced (essentially a linked list), the recursion depth can reach n, requiring O(n) space on the call stack. For a balanced binary search tree, the space complexity would be O(log n) due to the recursion depth being proportional to the tree height, but we consider the worst-case scenario here.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrectly Identifying Which Nodes to Mark as first and second

A common mistake is confusion about which node to assign to first and second when a violation is detected. When prev.val > root.val:

Wrong approach:

if prev.val > root.val:
    if first is None:
        first = root  # WRONG: should be prev
        second = prev  # WRONG: should be root

Why it's wrong: In the first violation, the larger value (which comes earlier in traversal) is the one that's out of place. That's prev, not root.

Correct approach:

if prev.val > root.val:
    if first is None:
        first = prev  # The node that appears too early (larger value)
    second = root    # The node that appears too late (smaller value)

2. Not Updating second for Every Violation

Another pitfall is only setting second once, similar to how first is handled:

Wrong approach:

if prev.val > root.val:
    if first is None:
        first = prev
        second = root  # WRONG: Only sets second on first violation

Why it's wrong: This fails when the swapped nodes are non-adjacent. In non-adjacent swaps, there are two violations, and second needs to be updated in the second violation.

Correct approach:

if prev.val > root.val:
    if first is None:
        first = prev
    second = root  # ALWAYS update second for each violation

3. Forgetting to Update prev After Processing Current Node

Wrong approach:

def dfs(root):
    if root is None:
        return
    dfs(root.left)
    if prev and prev.val > root.val:
        # violation detection logic
    # MISSING: prev = root
    dfs(root.right)

Why it's wrong: Without updating prev, you'll always compare against the same node, missing violations and incorrectly identifying swapped nodes.

Correct approach:

def dfs(root):
    if root is None:
        return
    dfs(root.left)
    if prev and prev.val > root.val:
        # violation detection logic
    prev = root  # Essential: Update prev for next comparison
    dfs(root.right)

4. Using Local Variables Instead of Nonlocal/Instance Variables

Wrong approach:

def recoverTree(self, root):
    def dfs(root):
        prev = None  # WRONG: Local variable, resets on each call
        first = None
        second = None
        # ... rest of logic

Why it's wrong: Local variables reset with each recursive call, losing track of nodes found in previous calls.

Correct approach:

def recoverTree(self, root):
    # Use instance variables
    self.prev = None
    self.first = None
    self.second = None
  
    # OR use nonlocal
    def dfs(root):
        nonlocal prev, first, second
        # ... rest of logic

5. Attempting to Return Modified Tree Instead of In-Place Modification

Wrong approach:

def recoverTree(self, root):
    # ... find first and second ...
    first.val, second.val = second.val, first.val
    return root  # WRONG: Problem asks for in-place modification, no return

Correct approach:

def recoverTree(self, root) -> None:  # Note: returns None
    # ... find first and second ...
    first.val, second.val = second.val, first.val
    # No return statement needed
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More