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 traversalfirst
: 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:
- We need to traverse the entire tree to identify the two swapped nodes
- In-order DFS traversal of a BST naturally gives us values in sorted order
- DFS allows us to visit each node exactly once while maintaining the context of previously visited nodes (using the
prev
variable) - 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:
- Do an in-order DFS traversal while keeping track of the previous node
- Whenever we find
prev.val > current.val
, we've found a violation - The first time we see a violation, mark the
prev
node as ourfirst
swapped node - Keep updating the
second
node to be the current node whenever we see a violation - After traversal, swap the values of
first
andsecond
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
, andsecond
prev
: Tracks the previously visited node during traversalfirst
: Stores the first node that appears out of ordersecond
: 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 markprev
as thefirst
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 EvaluatorExample 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
-
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
-
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
-
Visit node 2
- Left subtree is None
- Check:
prev.val (3) > root.val (2)
? Yes! First violation found - Since
first
is None, setfirst = prev
(node with value 3) - Set
second = root
(node with value 2) - Update:
prev = node(2)
- Right subtree is None
-
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
-
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 3second
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
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests
Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the
Want a Structured Path to Master System Design Too? Don’t Miss This!