Recover Binary Search Tree solution and explanation
Google
9 more videos on this problem
Recover Binary Search Tree (with Follow Up) | Live Coding with Explanation | Leetcode #99Algorithms Made Easy · 16:55 · 16K views
Leetcode - Recover Binary Search Tree (Python)Timothy H Chang · 5:49 · 9K views
Recover Binary Search Tree | LeetCode 99 | Programming TutorialsProgramming Tutorials · 15:47 · 9K views
Recover Binary Search Tree | Leetcode 99 | BST | Day-19Ayushi Sharma · 15:54 · 7K views
Recover Binary Search Tree | Leet code 99 | Theory explained + Python codeSai Anish Malla · 25:45 · 3K views
LeetCode 99. Recover Binary Search TreeHappy Coding · 48:11 · 1K views
Recover Binary Search Tree | Leetcode 99 | leetcode solutionEasyLeetcode · 10:54 · 707 views
LeetCode 99. Recover Binary Search Tree | JSer - Front-End Interview questionsJSer · 12:36 · 449 views
LeetCode99RecoverBinarySearchTree - Solution to LeetCode 99 - Recover Binary Search TreeLEETCODE MASTER · 14:30 · 349 views
LeetCode 99. [HARD] Recover Binary Search TreeFrancesco Manicardi · 8:48 · 270 views
The problem
You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.
Example 1:
Input: root = [1,3,null,null,2] Output: [3,1,null,null,2] Explanation: 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] Explanation: 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
O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?Approach overview
Problem Overview: A valid Binary Search Tree (BST) has an in-order traversal that produces a sorted sequence. In this problem, exactly two nodes in the BST were swapped by mistake. Your task is to restore the tree without changing its structure by identifying those two nodes and swapping their values back.
Approach 1: In-Order Traversal with Additional Space (O(n) time, O(n) space)
A straightforward approach is to perform an in-order traversal and store all node references in an array. Because a correct BST produces a sorted order, any swapped nodes will appear as violations where prev.val > curr.val. Iterate through the collected list and record the two positions where this ordering breaks. The first incorrect node is the larger value from the first violation, and the second node is the smaller value from the last violation. After identifying both nodes, swap their values to recover the BST. This method is simple and easy to reason about but uses O(n) additional memory to store the traversal.
This approach relies heavily on properties of a Binary Search Tree and uses a standard Depth-First Search traversal to collect nodes in sorted order.
Approach 2: Morris Traversal for Constant Space Complexity (O(n) time, O(1) space)
The optimal approach performs the same in-order traversal but without recursion or an auxiliary array. Morris Traversal temporarily modifies the tree structure by creating threaded links to predecessor nodes. While traversing, keep track of the previous visited node and detect ordering violations where prev.val > curr.val. The first time this happens, store prev as the first misplaced node. For the second violation, store curr as the second node. After the traversal finishes, swap the values of these two nodes.
Morris Traversal works because it simulates the call stack used in recursive tree traversal by reusing null pointers as temporary links. Each edge is visited at most twice, keeping the time complexity at O(n) while reducing space usage to O(1). This makes it ideal when memory constraints matter or when interviewers specifically ask for constant space.
Recommended for interviews: Start by explaining the in-order traversal idea since it directly leverages the sorted property of BSTs. That shows you understand the core invariant. Then move to Morris Traversal as the optimized solution with O(1) extra space. Interviewers usually expect the constant-space approach because it demonstrates deeper knowledge of tree traversal techniques.
Approach 1: In-Order Traversal with Additional Space
This approach uses an additional list to store the nodes during an in-order traversal of the BST. The in-order traversal yields the values of the BST in a sorted manner for a correct BST configuration. If two nodes have been swapped, this sorted order will be violated in exactly two places. By storing all nodes during traversal and comparing them, we can identify the two swapped nodes. Once identified, we swap their values to correct the tree.
This method requires O(n) space to store the nodes' values where n is the number of nodes in the tree.
class Solution:
def recoverTree(self, root: TreeNode) -> None:
def inorder(node):
return inorder(node.left) + [node] + inorder(node.right) if node else []
nodes = inorder(root)
x = y = None
for i in range(1, len(nodes)):
if nodes[i].val < nodes[i - 1].val:
y = nodes[i]
if x is None:
x = nodes[i - 1]
else:
break
x.val, y.val = y.val, x.valimport java.util.*;
class Solution {
public void recoverTree(TreeNode root) {
List<TreeNode> nodes = new ArrayList<>();
inorder(root, nodes);
TreeNode x = null, y = null;
for (int i = 1; i < nodes.size(); i++) {
if (nodes.get(i).val < nodes.get(i - 1).val) {
y = nodes.get(i);
if (x == null) {
x = nodes.get(i - 1);
} else break;
}
}
int temp = x.val;
x.val = y.val;
y.val = temp;
}
private void inorder(TreeNode node, List<TreeNode> nodes) {
if (node == null) return;
inorder(node.left, nodes);
nodes.add(node);
inorder(node.right, nodes);
}
}#include <vector>
using namespace std;
class Solution {
public:
void recoverTree(TreeNode* root) {
vector<TreeNode*> nodes;
TreeNode *x = nullptr, *y = nullptr;
inorder(root, nodes);
for (int i = 1; i < nodes.size(); ++i) {
if (nodes[i]->val < nodes[i-1]->val) {
y = nodes[i];
if (x == nullptr) x = nodes[i - 1];
else break;
}
}
swap(x->val, y->val);
}
void inorder(TreeNode* node, vector<TreeNode*>& nodes) {
if (!node) return;
inorder(node->left, nodes);
nodes.push_back(node);
inorder(node->right, nodes);
}
};var recoverTree = function(root) {
const nodes = [];
inorder(root, nodes);
let first = null, second = null;
for (let i = 0; i < nodes.length - 1; i++) {
if (nodes[i].val > nodes[i + 1].val) {
second = nodes[i + 1];
if (!first) first = nodes[i];
else break;
}
}
[first.val, second.val] = [second.val, first.val];
};
function inorder(node, nodes) {
if (!node) return;
inorder(node.left, nodes);
nodes.push(node);
inorder(node.right, nodes);
}#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void inorder(TreeNode* node, TreeNode** nodes, int* index) {
if (!node) return;
inorder(node->left, nodes, index);
nodes[(*index)++] = node;
inorder(node->right, nodes, index);
}
void recoverTree(TreeNode* root) {
TreeNode* nodes[1000];
int index = 0;
inorder(root, nodes, &index);
TreeNode *x = NULL, *y = NULL;
for (int i = 1; i < index; ++i) {
if (nodes[i]->val < nodes[i-1]->val) {
y = nodes[i];
if (!x) x = nodes[i - 1];
else break;
}
}
int temp = x->val;
x->val = y->val;
y->val = temp;
}using System.Collections.Generic;
public class Solution {
public void RecoverTree(TreeNode root) {
List<TreeNode> nodes = new List<TreeNode>();
Inorder(root, nodes);
TreeNode x = null, y = null;
for (int i = 1; i < nodes.Count; i++) {
if (nodes[i].val < nodes[i - 1].val) {
y = nodes[i];
if (x == null) {
x = nodes[i - 1];
} else break;
}
}
int temp = x.val;
x.val = y.val;
y.val = temp;
}
private void Inorder(TreeNode node, List<TreeNode> nodes) {
if (node == null) return;
Inorder(node.left, nodes);
nodes.Add(node);
Inorder(node.right, nodes);
}
}This Python solution performs an in-order traversal of the BST and stores the nodes in a list. It then iterates through this list to find the two nodes that are out of order, i.e., the swapped nodes, by checking where the current node value is less than the previous node value. Finally, it swaps the values of these nodes to correct the BST.
Time Complexity: O(n) since we are conducting an in-order traversal of the tree.
Space Complexity: O(n) as we store nodes in a list for comparison.
Approach 2: Morris Traversal for Constant Space Complexity
This approach leverages Morris Traversal to achieve O(1) space complexity, without needing an auxiliary stack or recursion. Morris Traversal utilizes the tree structure itself to keep track of nodes and ensures the tree is reset to its original configuration after traversal. To correct the BST, we detect swapped nodes by identifying violation of BST properties during traversal, and then we swap these nodes to achieve a valid BST.
class Solution:
def recoverTree(self, root: TreeNode) -> None:
first = second = prev = None
current = root
while current:
if current.left is None:
if prev and current.val < prev.val:
second = current
if first is None:
first = prev
prev = current
current = current.right
else:
pre = current.left
while pre.right and pre.right != current:
pre = pre.right
if pre.right is None:
pre.right = current
current = current.left
else:
pre.right = None
if prev and current.val < prev.val:
second = current
if first is None:
first = prev
prev = current
current = current.right
first.val, second.val = second.val, first.valclass Solution {
public void recoverTree(TreeNode root) {
TreeNode first = null, second = null, prev = null;
TreeNode current = root;
while (current != null) {
if (current.left == null) {
if (prev != null && current.val < prev.val) {
second = current;
if (first == null) first = prev;
}
prev = current;
current = current.right;
} else {
TreeNode pre = current.left;
while (pre.right != null && pre.right != current) pre = pre.right;
if (pre.right == null) {
pre.right = current;
current = current.left;
} else {
pre.right = null;
if (prev != null && current.val < prev.val) {
second = current;
if (first == null) first = prev;
}
prev = current;
current = current.right;
}
}
}
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;
TreeNode* current = root;
while (current) {
if (!current->left) {
if (prev && current->val < prev->val) {
second = current;
if (!first) first = prev;
}
prev = current;
current = current->right;
} else {
TreeNode* pre = current->left;
while (pre->right && pre->right != current) pre = pre->right;
if (!pre->right) {
pre->right = current;
current = current->left;
} else {
pre->right = nullptr;
if (prev && current->val < prev->val) {
second = current;
if (!first) first = prev;
}
prev = current;
current = current->right;
}
}
}
swap(first->val, second->val);
}
};function recoverTree(root) {
let first = null, second = null, prev = null;
let current = root;
while (current) {
if (!current.left) {
if (prev && current.val < prev.val) {
second = current;
if (!first) first = prev;
}
prev = current;
current = current.right;
} else {
let pre = current.left;
while (pre.right && pre.right !== current) pre = pre.right;
if (!pre.right) {
pre.right = current;
current = current.left;
} else {
pre.right = null;
if (prev && current.val < prev.val) {
second = current;
if (!first) first = prev;
}
prev = current;
current = current.right;
}
}
}
[first.val, second.val] = [second.val, first.val];
}#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void recoverTree(struct TreeNode* root) {
struct TreeNode *first = NULL, *second = NULL, *prev = NULL;
struct TreeNode* current = root;
while (current) {
if (!current->left) {
if (prev && current->val < prev->val) {
second = current;
if (!first) first = prev;
}
prev = current;
current = current->right;
} else {
struct TreeNode* pre = current->left;
while (pre->right && pre->right != current) pre = pre->right;
if (!pre->right) {
pre->right = current;
current = current->left;
} else {
pre->right = NULL;
if (prev && current->val < prev->val) {
second = current;
if (!first) first = prev;
}
prev = current;
current = current->right;
}
}
}
int temp = first->val;
first->val = second->val;
second->val = temp;
}public class Solution {
public void RecoverTree(TreeNode root) {
TreeNode first = null, second = null, prev = null;
TreeNode current = root;
while (current != null) {
if (current.left == null) {
if (prev != null && current.val < prev.val) {
second = current;
if (first == null) first = prev;
}
prev = current;
current = current.right;
} else {
TreeNode pre = current.left;
while (pre.right != null && pre.right != current) pre = pre.right;
if (pre.right == null) {
pre.right = current;
current = current.left;
} else {
pre.right = null;
if (prev != null && current.val < prev.val) {
second = current;
if (first == null) first = prev;
}
prev = current;
current = current.right;
}
}
}
int temp = first.val;
first.val = second.val;
second.val = temp;
}
}This Python solution uses Morris Inorder Traversal, which leverages the threads in the tree structure to avoid using additional space. While traversing, we establish temporary links (threads) to visiting nodes using their predecessor relations. We detect unordered node pairs and correct them by swapping their values.
Time Complexity: O(n).
Space Complexity: O(1).
Approach 3: In-order Traversal
In-order traversal of a binary search tree results in an increasing sequence. If two nodes' values are mistakenly swapped, there will definitely be two reverse pairs in the sequence obtained from the in-order traversal. We use first and second to record the smaller and larger values of these two reverse pairs, respectively. Finally, swapping the values of these two nodes will correct the mistake.
The time complexity is O(n), and the space complexity is O(n). Here, n is the number of nodes in the binary search tree.
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func recoverTree(root *TreeNode) {
var prev, first, second *TreeNode
var dfs func(*TreeNode)
dfs = func(root *TreeNode) {
if root == nil {
return
}
dfs(root.Left)
if prev != nil && prev.Val > root.Val {
if first == nil {
first = prev
}
second = root
}
prev = root
dfs(root.Right)
}
dfs(root)
first.Val, second.Val = second.Val, first.Val
}Complexity comparison
| Approach | Complexity |
|---|---|
| In-Order Traversal with Additional Space | Time Complexity: O(n) since we are conducting an in-order traversal of the tree. |
| Morris Traversal for Constant Space Complexity | Time Complexity: O(n). |
| In-order Traversal | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| In-Order Traversal with Array | O(n) | O(n) | Best for clarity and quick implementation when extra memory is acceptable. |
| Morris Traversal (Constant Space) | O(n) | O(1) | Preferred in interviews when constant auxiliary space is required. |
Frequently asked questions
Is Recover Binary Search Tree easy or hard?
Recover Binary Search Tree is rated Medium on LeetCode. Detecting swapped nodes using in-order traversal is straightforward, but implementing the optimal O(1) space Morris Traversal requires deeper understanding of tree traversal techniques.
Recover Binary Search Tree Python/Java solution
Typical Python or Java solutions perform an in-order traversal, track the previous node, and detect two nodes where the sorted order breaks. After traversal, swapping those node values restores the BST in O(n) time.
How to solve Recover Binary Search Tree in O(n)?
Perform an in-order traversal and track the previous visited node. Whenever prev.val is greater than the current node value, record the misplaced nodes. After traversal finishes, swap the values of the two identified nodes to restore the BST.
What is the best approach for Recover Binary Search Tree?
Morris Traversal is considered the best approach because it recovers the BST in O(n) time using O(1) extra space. It performs an in-order traversal without recursion or a stack while detecting the two misplaced nodes through ordering violations.
Is Recover Binary Search Tree asked at Google/Amazon/Meta?
Recover Binary Search Tree is a common interview problem at companies like Amazon, Google, and Meta because it tests understanding of BST properties, in-order traversal, and space optimization techniques like Morris Traversal.
What data structure is used in Recover Binary Search Tree?
The problem operates on a Binary Search Tree. The solution relies on in-order traversal, which can be implemented using recursion, an explicit stack, or Morris Traversal for constant auxiliary space.
What is the time complexity of Recover Binary Search Tree?
Both common solutions run in O(n) time where n is the number of nodes in the tree. Each node is visited at most once during the in-order traversal used to detect the swapped nodes.