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.

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.

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

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