Log inSign up
mediumLeetCodeNot Started

Recover Binary Search Tree

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

BST
Solve on LeetCode
Lesson

Problem Statement

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.

Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?

Constraints:

  • The number of nodes in the tree is in the range [2, 1000].
  • -231 <= Node.val <= 231 - 1

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Identify inversions in sorted sequences created by swapping two elements.
  • Implement the 3-pointer inversion tracking (first, middle, last).
  • Apply Morris Traversal to achieve strictly O(1) space.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Two nodes swapped in BST.
  • Recover tree in-place without changing structure.
  • O(1) space follow-up requirement.

Algorithmic Decision Tree:

  • Track prev during inorder traversal.
  • When prev.val > curr.val: record first = prev, middle = curr on 1st drop, and last = curr on 2nd drop.
  • Swap values of first and (last != null ? last : middle).

Connected Patterns:

Validate Binary Search TreeMorris Inorder TraversalFind Median of BST

1. Inorder Array Extraction + Re-sort

Intuition

Perform an inorder traversal, storing all node references in nodes and their values in vals. Sort vals. Iterate through nodes and assign nodes[i].val = vals[i]. Takes O(N log N) time and O(N) space.

When to apply: Baseline comparison when O(N) memory is unrestricted.

Algorithm

  1. Collect all node references and their values in arrays, sort the values, and rewrite values to nodes in-order.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct TreeNode {
6 int val;
7 TreeNode* left;
8 TreeNode* right;
9 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10};
11
12class Solution {
13 void inorder(TreeNode* root, std::vector<TreeNode*>& nodes, std::vector<int>& vals) {
14 if (!root) return;
15 inorder(root->left, nodes, vals);
16 nodes.push_back(root);
17 vals.push_back(root->val);
18 inorder(root->right, nodes, vals);
19 }
20public:
21 void recoverTree(TreeNode* root) {
22 std::vector<TreeNode*> nodes;
23 std::vector<int> vals;
24 inorder(root, nodes, vals);
25
26 std::sort(vals.begin(), vals.end());
27 for (int i = 0; i < (int)nodes.size(); i++) {
28 nodes[i]->val = vals[i];
29 }
30 }
31};
32
33int main() {
34 TreeNode* root = new TreeNode(1);
35 root->left = new TreeNode(3);
36 root->left->right = new TreeNode(2);
37
38 Solution sol;
39 sol.recoverTree(root);
40 std::cout << "Root: " << root->val << " (Left: " << root->left->val << ")" << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N log N)
  • Space complexity: O(N)

2. Recursive Inorder DFS with Previous Pointer

Intuition

Maintain global/instance pointers prev, first, middle, last. Run recursive inorder DFS: 1. Visit left. 2. If prev != null && prev.val > curr.val: if first == null, set first = prev and middle = curr; else set last = curr. Update prev = curr. 3. Visit right. 4. After DFS completes, swap values of first and (last ? last : middle). Runs in O(N) time and O(H) stack space.

When to apply: Standard interview approach when O(H) recursion stack is allowed.

Algorithm

  1. Track prev during recursive inorder traversal; locate first, middle, and last drop nodes, then swap values.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <algorithm>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12 TreeNode *first = nullptr, *middle = nullptr, *last = nullptr, *prev = nullptr;
13
14 void inorder(TreeNode* root) {
15 if (!root) return;
16
17 inorder(root->left);
18
19 if (prev && prev->val > root->val) {
20 if (!first) {
21 first = prev;
22 middle = root;
23 } else {
24 last = root;
25 }
26 }
27 prev = root;
28
29 inorder(root->right);
30 }
31public:
32 void recoverTree(TreeNode* root) {
33 first = middle = last = prev = nullptr;
34 inorder(root);
35
36 if (first && last) {
37 std::swap(first->val, last->val);
38 } else if (first && middle) {
39 std::swap(first->val, middle->val);
40 }
41 }
42};
43
44int main() {
45 TreeNode* root = new TreeNode(1);
46 root->left = new TreeNode(3);
47 root->left->right = new TreeNode(2);
48
49 Solution sol;
50 sol.recoverTree(root);
51 std::cout << "Root: " << root->val << " (Left: " << root->left->val << ")" << std::endl;
52 return 0;
53}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(H) recursion stack space

3. Morris Inorder Traversal (O(1) Auxiliary Space)

Intuition

1. Maintain first, middle, last, prev. 2. Perform Morris Inorder Traversal: - When visiting curr: if prev && prev.val > curr.val, record first = prev, middle = curr on 1st drop, and last = curr on 2nd drop. Update prev = curr. 3. Restore all temporary threads before terminating. 4. Swap values of first and (last ? last : middle). Achieves linear O(N) runtime and strictly O(1) auxiliary space.

When to apply: Optimal solution answering the follow-up question for strictly O(1) auxiliary space.

Algorithm

  1. Execute Morris Traversal to inspect nodes in ascending order in O(1) space, detecting inversions and swapping node values.

Morris Traversal Recover BST Trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
At 3 -> 2: 3 > 2 (1st drop)
Visual state
Values and pointers at this exact step
tree
This tree trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Check / comparison
Inorder sequence: 3 -> 2 -> 1
Decision / next transition
1
Why this step matters

At 3 -> 2: 3 > 2 (1st drop). first = 3, middle = 2.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <algorithm>
3
4struct TreeNode {
5 int val;
6 TreeNode* left;
7 TreeNode* right;
8 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9};
10
11class Solution {
12public:
13 void recoverTree(TreeNode* root) {
14 TreeNode *first = nullptr, *middle = nullptr, *last = nullptr, *prev = nullptr;
15 TreeNode *curr = root;
16
17 while (curr) {
18 if (!curr->left) {
19 if (prev && prev->val > curr->val) {
20 if (!first) {
21 first = prev;
22 middle = curr;
23 } else {
24 last = curr;
25 }
26 }
27 prev = curr;
28 curr = curr->right;
29 } else {
30 TreeNode* pre = curr->left;
31 while (pre->right && pre->right != curr) {
32 pre = pre->right;
33 }
34
35 if (!pre->right) {
36 pre->right = curr;
37 curr = curr->left;
38 } else {
39 pre->right = nullptr;
40 if (prev && prev->val > curr->val) {
41 if (!first) {
42 first = prev;
43 middle = curr;
44 } else {
45 last = curr;
46 }
47 }
48 prev = curr;
49 curr = curr->right;
50 }
51 }
52 }
53
54 if (first && last) {
55 std::swap(first->val, last->val);
56 } else if (first && middle) {
57 std::swap(first->val, middle->val);
58 }
59 }
60};
61
62int main() {
63 TreeNode* root = new TreeNode(1);
64 root->left = new TreeNode(3);
65 root->left->right = new TreeNode(2);
66
67 Solution sol;
68 sol.recoverTree(root);
69 std::cout << "Root: " << root->val << " (Left: " << root->left->val << ")" << std::endl;
70 return 0;
71}

Time & Space Complexity

  • Time complexity: O(N)
  • Space complexity: O(1) auxiliary space

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Inorder Array Extraction + Re-sortO(N log N)O(N)Collect all node references and their values in arrays, sort the values, and rewrite values to nodes in-order.O(N log N)
2.Recursive Inorder DFS with Previous PointerO(N)O(H) recursion stack spaceTrack prev during recursive inorder traversal; locate first, middle, and last drop nodes, then swap values.O(N)
3.Morris Inorder Traversal (O(1) Auxiliary Space)OptimalO(N)O(1) auxiliary spaceExecute Morris Traversal to inspect nodes in ascending order in O(1) space, detecting inversions and swapping node values.O(N)

Common Pitfalls & Crucial Edge Cases

Swapping node references instead of values

Swapping pointers in a tree requires rewiring parent and child pointers; swapping values is far simpler and required by the problem statement.

Assuming there will always be 2 drops

Fails on adjacent swaps where only 1 drop occurs.

Breaking out of Morris traversal early

Leaves corrupted threaded pointers in the tree.

Crucial Edge Cases to Validate:

  • Adjacent nodes swapped (`[1, 3, 2, 4]`) — Handled via first and middle swap.
  • Non-adjacent nodes swapped (`[1, 5, 3, 4, 2]`) — Handled via first and last swap.
  • Root is one of the swapped nodes — Handled seamlessly by value swap.
  • Two-node tree — Single inversion; swaps the two nodes.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Explain the two inversion cases clearly on the whiteboard: non-adjacent (2 drops) vs adjacent (1 drop).
  2. Mention that value swap is permitted ('recover the tree without changing its structure').
  3. Offer Morris Traversal as the answer to the follow-up O(1) space question.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.How many inversions (drops where prev.val > curr.val) occur when two NON-adjacent nodes are swapped in a BST?

2.If two ADJACENT nodes are swapped in a BST, how many inversions occur?

3.Why does Morris Traversal achieve O(1) space?

Back to DSA Sheet