Recover Binary Search Tree (Two Nodes Swapped)

🎯

Recover Binary Search Tree (Two Nodes Swapped)

hardTREEAmazonGoogleMicrosoft

Imagine a database index tree where two entries got swapped by mistake, causing queries to return incorrect results. Fixing the tree without rebuilding it from scratch is crucial for performance.

💡 This problem involves correcting a binary search tree (BST) where exactly two nodes have been swapped, breaking the BST property. Beginners often struggle because the BST property is global but the violation is local and subtle, requiring careful traversal and identification of misplaced nodes.

📋

Problem Statement

Given the root of a binary search tree (BST), where exactly two nodes have been swapped by mistake, recover the tree without changing its structure. Return nothing; modify the tree in-place.

The number of nodes in the tree is in the range [1, 10^5].Node values are unique.Exactly two nodes of the tree were swapped.You must solve the problem without changing the tree structure.

💡

Example

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

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

The nodes with values 1 and 3 are swapped. After recovery, the BST property is restored.

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

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

Nodes 2 and 3 are swapped. Fixing them restores the BST.

• Tree with only two nodes swapped at root and one child → should swap back
• Swapped nodes are adjacent in inorder traversal → simple swap
• Swapped nodes are far apart in inorder traversal → requires identifying two violations
• Tree with only one node → no change needed

⚠️

Common Mistakes

Swapping node values before identifying both nodes

Incorrect fix if only one violation detected, missing second swapped node

✅ Wait until traversal completes to swap values of both identified nodes

Not handling adjacent swapped nodes correctly

Only one violation detected, second node not updated properly

✅ Update second node on first violation and again if second violation occurs

Using extra space unnecessarily in optimal approach

Increased memory usage, losing O(1) space advantage

✅ Use Morris traversal or pointer tracking without arrays or stacks

Modifying tree structure permanently during Morris traversal

Tree becomes corrupted after function ends

✅ Always revert temporary threads (pred.right) to null after use

Not considering edge cases like single node or no swaps

Code may crash or swap wrong nodes

✅ Add null checks and handle trivial cases gracefully

🧠

Brute Force (Inorder Traversal + Sorting)

💡 This approach exists to build intuition by leveraging the BST property that inorder traversal yields sorted values. Beginners learn how the violation appears as disorder in the inorder sequence.

Intuition

Perform an inorder traversal to get the node values in an array, sort the array to get the correct order, then assign the sorted values back to the nodes in inorder sequence.

Algorithm

1. Perform inorder traversal and store node values in a list.
2. Sort the list to get the correct node values order.
3. Perform inorder traversal again, replacing node values with sorted values.

💡 The challenge is to realize that inorder traversal linearizes the BST, and sorting fixes the swapped values, but this approach uses extra space and is not in-place.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def recoverTree(root):
    vals = []
    def inorder(node):
        if not node:
            return
        inorder(node.left)
        vals.append(node.val)
        inorder(node.right)
    inorder(root)
    sorted_vals = sorted(vals)
    i = 0
    def inorder_replace(node):
        nonlocal i
        if not node:
            return
        inorder_replace(node.left)
        node.val = sorted_vals[i]
        i += 1
        inorder_replace(node.right)
    inorder_replace(root)

# Example usage:
# root = TreeNode(1, TreeNode(3, None, TreeNode(2)))
# recoverTree(root)
# After calling recoverTree, the tree is fixed.

Line Notes

vals = []Initialize list to store inorder values

def inorder(node):Define helper to traverse tree inorder

vals.append(node.val)Collect node values in inorder sequence

sorted_vals = sorted(vals)Sort values to get correct BST order

def inorder_replace(node):Helper to assign sorted values back to nodes

node.val = sorted_vals[i]Replace node value with correct sorted value

i += 1Move to next index in sorted values

inorder_replace(root)Start second inorder traversal to replace values

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class Solution {
    List<Integer> vals = new ArrayList<>();
    int i = 0;
    public void recoverTree(TreeNode root) {
        inorder(root);
        List<Integer> sortedVals = new ArrayList<>(vals);
        Collections.sort(sortedVals);
        i = 0;
        inorderReplace(root, sortedVals);
    }
    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        vals.add(node.val);
        inorder(node.right);
    }
    private void inorderReplace(TreeNode node, List<Integer> sortedVals) {
        if (node == null) return;
        inorderReplace(node.left, sortedVals);
        node.val = sortedVals.get(i++);
        inorderReplace(node.right, sortedVals);
    }
    // Example main method
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.right = new TreeNode(2);
        new Solution().recoverTree(root);
        // Tree is fixed after recoverTree
    }
}

Line Notes

List<Integer> vals = new ArrayList<>()Store inorder node values

inorder(root)Traverse tree inorder to collect values

Collections.sort(sortedVals)Sort values to restore BST order

node.val = sortedVals.get(i++)Assign sorted value back to node

if (node == null) returnBase case for recursion to avoid null pointer

i = 0Reset index before second traversal

inorderReplace(root, sortedVals)Start second inorder traversal to replace values

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
    vector<int> vals;
    int i = 0;
public:
    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        vals.push_back(node->val);
        inorder(node->right);
    }
    void inorderReplace(TreeNode* node, vector<int>& sortedVals) {
        if (!node) return;
        inorderReplace(node->left, sortedVals);
        node->val = sortedVals[i++];
        inorderReplace(node->right, sortedVals);
    }
    void recoverTree(TreeNode* root) {
        inorder(root);
        vector<int> sortedVals = vals;
        sort(sortedVals.begin(), sortedVals.end());
        i = 0;
        inorderReplace(root, sortedVals);
    }
};
// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(3);
//     root->left->right = new TreeNode(2);
//     Solution().recoverTree(root);
//     return 0;
// }

Line Notes

vector<int> vals;Store inorder traversal values

void inorder(TreeNode* node)Recursive inorder traversal to collect values

vals.push_back(node->val);Add current node's value to list

sort(sortedVals.begin(), sortedVals.end());Sort values to fix swapped nodes

node->val = sortedVals[i++];Assign sorted value back to node

if (!node) return;Base case to stop recursion

inorderReplace(root, sortedVals);Start second inorder traversal to replace values

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}
function recoverTree(root) {
    const vals = [];
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        vals.push(node.val);
        inorder(node.right);
    }
    inorder(root);
    const sortedVals = [...vals].sort((a,b) => a-b);
    let i = 0;
    function inorderReplace(node) {
        if (!node) return;
        inorderReplace(node.left);
        node.val = sortedVals[i++];
        inorderReplace(node.right);
    }
    inorderReplace(root);
}
// Example usage:
// let root = new TreeNode(1, new TreeNode(3, null, new TreeNode(2)));
// recoverTree(root);
// Tree is fixed after recoverTree

Line Notes

const vals = []Array to store inorder node values

function inorder(node)Helper to traverse tree inorder

vals.push(node.val)Collect node values in inorder sequence

const sortedVals = [...vals].sort((a,b) => a-b)Sort values to restore BST order

node.val = sortedVals[i++]Replace node value with correct sorted value

if (!node) returnBase case to stop recursion

inorderReplace(root)Start second inorder traversal to replace values

⏱

Complexity

TimeO(n log n)

SpaceO(n)

Inorder traversal takes O(n), sorting takes O(n log n), and second traversal O(n). Overall dominated by sorting.

💡 For n=1000 nodes, sorting 1000 values is about 10,000 operations, which is inefficient compared to linear solutions.

Interview Verdict: Accepted but inefficient

This approach works but is not optimal; it uses extra space and sorting, which can be improved.

🧠

Better (Inorder Traversal with Two Pointers)

💡 This approach improves on brute force by detecting the two swapped nodes during a single inorder traversal, avoiding sorting and extra space for values.

Intuition

Since inorder traversal of BST is sorted, swapped nodes cause violations where a previous node's value is greater than the current node's value. Detect these violations to identify the two swapped nodes and swap their values back.

Algorithm

1. Initialize pointers: prev (previous node), first and second (nodes to swap).
2. Traverse the tree inorder, comparing current node value with prev node value.
3. When a violation is found (prev.val > current.val), record nodes: first violation sets first and second, second violation updates second.
4. After traversal, swap the values of first and second nodes.

💡 The tricky part is understanding that there can be one or two violations depending on whether swapped nodes are adjacent or not, and how to track them correctly.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def recoverTree(root):
    first = second = prev = None
    def inorder(node):
        nonlocal first, second, prev
        if not node:
            return
        inorder(node.left)
        if prev and prev.val > node.val:
            if not first:
                first = prev
                second = node
            else:
                second = node
        prev = node
        inorder(node.right)
    inorder(root)
    first.val, second.val = second.val, first.val

# Example usage:
# root = TreeNode(1, TreeNode(3, None, TreeNode(2)))
# recoverTree(root)
# Tree is fixed after recoverTree

Line Notes

first = second = prev = NoneInitialize pointers to track swapped nodes and previous node

def inorder(node):Recursive inorder traversal helper

if prev and prev.val > node.val:Detect violation where BST property breaks

if not first:First violation found, record first and second nodes

else:Second violation found, update second node

prev = nodeUpdate prev to current node for next comparison

first.val, second.val = second.val, first.valSwap the values of the two nodes to fix BST

inorder(root)Start inorder traversal from root

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class Solution {
    TreeNode first = null, second = null, prev = null;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        if (prev != null && prev.val > node.val) {
            if (first == null) {
                first = prev;
                second = node;
            } else {
                second = node;
            }
        }
        prev = node;
        inorder(node.right);
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.right = new TreeNode(2);
        new Solution().recoverTree(root);
    }
}

Line Notes

TreeNode first = null, second = null, prev = null;Pointers to track swapped nodes and previous node

if (prev != null && prev.val > node.val)Detect violation in inorder traversal

if (first == null)First violation found, record first and second

elseSecond violation found, update second node

prev = node;Update prev for next comparison

int temp = first.val;Swap values of first and second nodes

inorder(root);Start inorder traversal from root

#include <iostream>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
    TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;
public:
    void inorder(TreeNode* node) {
        if (!node) return;
        inorder(node->left);
        if (prev && prev->val > node->val) {
            if (!first) {
                first = prev;
                second = node;
            } else {
                second = node;
            }
        }
        prev = node;
        inorder(node->right);
    }
    void recoverTree(TreeNode* root) {
        inorder(root);
        swap(first->val, second->val);
    }
};
// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(3);
//     root->left->right = new TreeNode(2);
//     Solution().recoverTree(root);
//     return 0;
// }

Line Notes

TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;Pointers to track swapped nodes and previous node

if (prev && prev->val > node->val)Detect violation in inorder traversal

if (!first)First violation found, record first and second

elseSecond violation found, update second

prev = node;Update prev for next comparison

swap(first->val, second->val);Swap values of the two nodes to fix BST

inorder(root);Start inorder traversal from root

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}
function recoverTree(root) {
    let first = null, second = null, prev = null;
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        if (prev && prev.val > node.val) {
            if (!first) {
                first = prev;
                second = node;
            } else {
                second = node;
            }
        }
        prev = node;
        inorder(node.right);
    }
    inorder(root);
    let temp = first.val;
    first.val = second.val;
    second.val = temp;
}
// Example usage:
// let root = new TreeNode(1, new TreeNode(3, null, new TreeNode(2)));
// recoverTree(root);
// Tree is fixed after recoverTree

Line Notes

let first = null, second = null, prev = null;Initialize pointers to track swapped nodes and previous node

if (prev && prev.val > node.val)Detect violation in inorder traversal

if (!first)First violation found, record first and second

elseSecond violation found, update second

prev = node;Update prev for next comparison

let temp = first.val;Swap values of the two nodes to fix BST

inorder(root);Start inorder traversal from root

⏱

Complexity

TimeO(n)

SpaceO(h)

Single inorder traversal takes O(n) time. Space is O(h) due to recursion stack, where h is tree height.

💡 For a balanced tree with 1000 nodes, recursion stack depth is about 10, so space is minimal.

Interview Verdict: Accepted and optimal for most cases

This approach is the standard solution and expected in interviews for its efficiency and clarity.

🧠

Optimal (Morris Inorder Traversal for O(1) Space)

💡 This approach uses Morris traversal to achieve inorder traversal without recursion or stack, reducing space to O(1). It is advanced but shows mastery of tree traversal techniques.

Intuition

Morris traversal temporarily modifies tree links to traverse inorder without extra space. Using the same violation detection logic, we find swapped nodes and fix them in-place.

Algorithm

1. Initialize pointers: first, second, prev, and current node.
2. While current is not null, if current has no left child, process current and move right.
3. If current has left child, find predecessor (rightmost node in left subtree).
4. If predecessor's right is null, set it to current and move current to left child.
5. If predecessor's right is current, revert it to null, process current, and move right.
6. During processing, detect violations as in previous approach.
7. After traversal, swap values of first and second nodes.

💡 The complexity is in threading and unthreading the tree while detecting violations without recursion or stack.

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def recoverTree(root):
    first = second = prev = None
    current = root
    while current:
        if not current.left:
            if prev and prev.val > current.val:
                if not first:
                    first = prev
                    second = current
                else:
                    second = current
            prev = current
            current = current.right
        else:
            pred = current.left
            while pred.right and pred.right != current:
                pred = pred.right
            if not pred.right:
                pred.right = current
                current = current.left
            else:
                pred.right = None
                if prev and prev.val > current.val:
                    if not first:
                        first = prev
                        second = current
                    else:
                        second = current
                prev = current
                current = current.right
    first.val, second.val = second.val, first.val

# Example usage:
# root = TreeNode(1, TreeNode(3, None, TreeNode(2)))
# recoverTree(root)
# Tree is fixed after recoverTree

Line Notes

current = rootStart traversal from root

if not current.left:If no left child, process current node directly

if prev and prev.val > current.val:Detect violation in inorder sequence

pred = current.leftFind predecessor in left subtree

while pred.right and pred.right != current:Find rightmost node in left subtree

pred.right = currentThread predecessor's right to current node

pred.right = NoneRemove temporary thread to restore tree

first.val, second.val = second.val, first.valSwap values of swapped nodes

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}
public class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode first = null, second = null, prev = null, current = root;
        while (current != null) {
            if (current.left == null) {
                if (prev != null && prev.val > current.val) {
                    if (first == null) {
                        first = prev;
                        second = current;
                    } else {
                        second = current;
                    }
                }
                prev = current;
                current = current.right;
            } else {
                TreeNode pred = current.left;
                while (pred.right != null && pred.right != current) {
                    pred = pred.right;
                }
                if (pred.right == null) {
                    pred.right = current;
                    current = current.left;
                } else {
                    pred.right = null;
                    if (prev != null && prev.val > current.val) {
                        if (first == null) {
                            first = prev;
                            second = current;
                        } else {
                            second = current;
                        }
                    }
                    prev = current;
                    current = current.right;
                }
            }
        }
        int temp = first.val;
        first.val = second.val;
        second.val = temp;
    }
    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(3);
        root.left.right = new TreeNode(2);
        new Solution().recoverTree(root);
    }
}

Line Notes

TreeNode first = null, second = null, prev = null, current = root;Initialize pointers for traversal and swapped nodes

if (current.left == null)If no left child, process current node

while (pred.right != null && pred.right != current)Find predecessor in left subtree

pred.right = current;Create temporary thread to current node

pred.right = null;Remove temporary thread to restore tree

int temp = first.val;Swap values of the two swapped nodes

while (current != null)Traverse until all nodes processed

#include <iostream>
using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *prev = nullptr, *current = root;
        while (current) {
            if (!current->left) {
                if (prev && prev->val > current->val) {
                    if (!first) {
                        first = prev;
                        second = current;
                    } else {
                        second = current;
                    }
                }
                prev = current;
                current = current->right;
            } else {
                TreeNode* pred = current->left;
                while (pred->right && pred->right != current) {
                    pred = pred->right;
                }
                if (!pred->right) {
                    pred->right = current;
                    current = current->left;
                } else {
                    pred->right = nullptr;
                    if (prev && prev->val > current->val) {
                        if (!first) {
                            first = prev;
                            second = current;
                        } else {
                            second = current;
                        }
                    }
                    prev = current;
                    current = current->right;
                }
            }
        }
        swap(first->val, second->val);
    }
};
// Example usage:
// int main() {
//     TreeNode* root = new TreeNode(1);
//     root->left = new TreeNode(3);
//     root->left->right = new TreeNode(2);
//     Solution().recoverTree(root);
//     return 0;
// }

Line Notes

TreeNode *first = nullptr, *second = nullptr, *prev = nullptr, *current = root;Initialize pointers for traversal and swapped nodes

if (!current->left)If no left child, process current node

while (pred->right && pred->right != current)Find predecessor in left subtree

pred->right = current;Create temporary thread to current node

pred->right = nullptr;Remove temporary thread to restore tree

swap(first->val, second->val);Swap values of the two swapped nodes

while (current)Traverse until all nodes processed

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}
function recoverTree(root) {
    let first = null, second = null, prev = null, current = root;
    while (current) {
        if (!current.left) {
            if (prev && prev.val > current.val) {
                if (!first) {
                    first = prev;
                    second = current;
                } else {
                    second = current;
                }
            }
            prev = current;
            current = current.right;
        } else {
            let pred = current.left;
            while (pred.right && pred.right !== current) {
                pred = pred.right;
            }
            if (!pred.right) {
                pred.right = current;
                current = current.left;
            } else {
                pred.right = null;
                if (prev && prev.val > current.val) {
                    if (!first) {
                        first = prev;
                        second = current;
                    } else {
                        second = current;
                    }
                }
                prev = current;
                current = current.right;
            }
        }
    }
    let temp = first.val;
    first.val = second.val;
    second.val = temp;
}
// Example usage:
// let root = new TreeNode(1, new TreeNode(3, null, new TreeNode(2)));
// recoverTree(root);
// Tree is fixed after recoverTree

Line Notes

let first = null, second = null, prev = null, current = root;Initialize pointers for traversal and swapped nodes

if (!current.left)If no left child, process current node

while (pred.right && pred.right !== current)Find predecessor in left subtree

pred.right = current;Create temporary thread to current node

pred.right = null;Remove temporary thread to restore tree

let temp = first.val;Swap values of the two swapped nodes

while (current)Traverse until all nodes processed

⏱

Complexity

TimeO(n)

SpaceO(1)

Morris traversal visits each node at most twice, so O(n) time. Space is O(1) as no recursion or stack is used.

💡 For large trees, this approach saves memory by avoiding recursion stack, which is critical in memory-constrained environments.

Interview Verdict: Accepted and optimal with O(1) space

This is the most advanced solution, demonstrating mastery of tree traversal and in-place algorithms.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code the second approach (inorder traversal with two pointers) for clarity and efficiency. Mention the brute force and Morris traversal as alternatives.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n log n)	O(n)	No	Yes	Mention only - never code
2. Better (Inorder Traversal with Two Pointers)	O(n)	O(h)	Yes (deep recursion)	Yes	Code this approach
3. Optimal (Morris Inorder Traversal)	O(n)	O(1)	No	Yes	Mention as follow-up

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain the brute force approach to show understanding, followed by the optimal approach. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach using inorder traversal and sorting.Step 3: Explain the better approach using inorder traversal with two pointers to detect swapped nodes.Step 4: If asked, discuss the Morris traversal approach for O(1) space.Step 5: Code the optimal approach and test with edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your understanding of BST properties, inorder traversal, ability to detect subtle violations, and your skill in writing clean, efficient code with correct edge case handling.

Common Follow-ups

• What if more than two nodes are swapped? → Requires more complex detection or rebuilding.
• Can you do it without recursion or stack? → Use Morris traversal for O(1) space.

💡 These follow-ups test deeper understanding of BST invariants and advanced traversal techniques.

🔍

Pattern Recognition

When to Use

1) Given a BST with exactly two nodes swapped, 2) Asked to fix the BST in-place, 3) Need to identify nodes violating inorder sorted order, 4) Optimize for time and space.

Signature Phrases

'Two nodes of a BST are swapped by mistake''Recover the tree without changing its structure'

NOT This Pattern When

Problems that require building BST from scratch or balancing BSTs are different patterns.

Similar Problems

Validate Binary Search Tree - checks if BST property holdsConvert BST to Greater Tree - modifies node values based on inorderRecover Binary Search Tree II - extension with multiple swapped nodes