Recover Binary Search Tree

Medium
1904.

Recover Binary Search Tree

Recover Binary Search Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Microsoft and Bloomberg interviews.

You are given the root of a binary search tree with distinct values in which exactly two nodes had their values swapped by mistake.

Repair the tree in place by swapping those two values back, without changing its shape, and return its root.

Example 1

Input
root = [1,3,null,null,2]
Output
[3,1,null,null,2]
Explanation
3 cannot be the left child of 1. Swapping 1 and 3 makes the tree 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. Swapping 2 and 3 makes the tree valid.

Example 3

Input
root = [2,3,1]
Output
[2,1,3]
Explanation
The two children were swapped with each other.

Constraints

  • 2 <= number of nodes <= 1000
  • -2^31 <= Node.val <= 2^31 - 1
  • all node values are distinct
  • the tree is a binary search tree after swapping exactly two values back

Follow-up: The direct way stores the in-order sequence in O(n) space. Can you do it with O(h) — or even O(1) — extra space?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {TreeNode}
 */
var recoverTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Recover Binary Search Tree — Solution in Python, Java & C++

Recover Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Recover Binary Search Tree is a medium coding problem on depth-first search and trees, asked in Amazon, Microsoft and Bloomberg interviews.

Problem statement

You are given the root of a binary search tree with distinct values in which exactly two nodes had their values swapped by mistake.

Repair the tree in place by swapping those two values back, without changing its shape, and return its root.

Example 1

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be the left child of 1. Swapping 1 and 3 makes the tree 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. Swapping 2 and 3 makes the tree valid.

Example 3

Input: root = [2,3,1]
Output: [2,1,3]
Explanation: The two children were swapped with each other.

Constraints

  • 2 <= number of nodes <= 1000
  • -2^31 <= Node.val <= 2^31 - 1
  • all node values are distinct
  • the tree is a binary search tree after swapping exactly two values back

Follow-up: The direct way stores the in-order sequence in O(n) space. Can you do it with O(h) — or even O(1) — extra space?

Hints for Recover Binary Search Tree

  1. Hint 1

    The in-order sequence of a binary search tree is sorted; here it is sorted except that two values traded places.

  2. Hint 2

    Walk in order and look for positions where a value is smaller than the one just before it. There are one or two such drops.

  3. Hint 3

    The first misplaced node is the larger value at the first drop; the second is the smaller value at the last drop. Swap their values.

How to solve Recover Binary Search Tree

Swapping two entries of a sorted sequence creates one drop (if they were neighbours) or two; the misplaced values are the left side of the first drop and the right side of the last one.

Approach

  1. Walk the tree in order with an explicit stack, remembering the previously visited node.
  2. Whenever prev.val > node.val: if no first node is recorded, record prev as the first; in every case record node as the second.
  3. After the walk, swap the values of the first and second nodes.
  4. Return the root.

Why it works

Let the sorted in-order sequence have entries at positions i < j exchanged. The larger value now sits at i, so position i is followed by a smaller value — the first drop's left side is position i. The smaller value sits at j, preceded by something larger — the last drop's right side is position j. When j = i + 1 these are the same single drop, which is why second is overwritten at every drop while first is set only once.

Complexity

  • Time — O(n)
  • Space — O(h) for the stack (Morris traversal brings it to O(1))

Pitfalls

  • Adjacent swapped values produce only one drop; record both nodes from it.
  • Swap the values, not the nodes — the shape must not change.

Reference solution

Python

from typing import Optional

def recoverTree(root: Optional[TreeNode]) -> Optional[TreeNode]:
    stack = []
    node = root
    prev = first = second = None
    while stack or node:
        while node:
            stack.append(node)
            node = node.left
        node = stack.pop()
        if prev is not None and prev.val > node.val:
            if first is None:
                first = prev
            second = node
        prev = node
        node = node.right
    first.val, second.val = second.val, first.val
    return root

Java

public static TreeNode recoverTree(TreeNode root) {
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode node = root, prev = null, first = null, second = null;
    while (!stack.isEmpty() || node != null) {
        while (node != null) { stack.push(node); node = node.left; }
        node = stack.pop();
        if (prev != null && prev.val > node.val) {
            if (first == null) first = prev;
            second = node;
        }
        prev = node;
        node = node.right;
    }
    int t = first.val;
    first.val = second.val;
    second.val = t;
    return root;
}

C++

TreeNode* recoverTree(TreeNode* root) {
    vector<TreeNode*> stack;
    TreeNode *node = root, *prev = nullptr, *first = nullptr, *second = nullptr;
    while (!stack.empty() || node) {
        while (node) { stack.push_back(node); node = node->left; }
        node = stack.back();
        stack.pop_back();
        if (prev && prev->val > node->val) {
            if (!first) first = prev;
            second = node;
        }
        prev = node;
        node = node->right;
    }
    swap(first->val, second->val);
    return root;
}

JavaScript

var recoverTree = function(root) {
    var stack = [], node = root, prev = null, first = null, second = null;
    while (stack.length > 0 || node !== null) {
        while (node !== null) { stack.push(node); node = node.left; }
        node = stack.pop();
        if (prev !== null && prev.val > node.val) {
            if (first === null) first = prev;
            second = node;
        }
        prev = node;
        node = node.right;
    }
    var t = first.val;
    first.val = second.val;
    second.val = t;
    return root;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals