Recover Binary Search Tree

Medium Trees & BST BST Basics Original on LeetCode

Recover Binary Search Tree is a medium trees & bst problem solved with the bst basics pattern. The best approach, optimal (morris in-order traversal), runs in O(n) time and O(1) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (collect, sort, write back) up.

Problem

You are given the root of a binary search tree in which the values of exactly two nodes were swapped by mistake. Every other node is where it should be.

Fix the tree in place by putting the two values back, without changing the tree’s shape. The function returns nothing; the tree itself is checked afterwards.

Examples

Example 1

Input
root = [4, 2, 6, 1, 5, 3, 7]
Output
[4, 2, 6, 1, 3, 5, 7]
Why
The in-order sequence is 1, 2, 5, 4, 3, 6, 7. Values 5 and 3 are in each other's places, so swapping them restores the order.

Example 2

Input
root = [2, null, 1]
Output
[1, null, 2]
Why
The root and its right child hold each other's values.

Example 3

Input
root = [3, 1, 4, null, null, 2]
Output
[2, 1, 4, null, null, 3]
Why
In-order gives 1, 3, 2, 4: the swapped values 3 and 2 sit next to each other in that sequence.

Constraints

  • The tree has 2 to 1000 nodes.
  • -2^31 <= Node.val <= 2^31 - 1, all values distinct.
  • Exactly two nodes have had their values swapped; everything else is a valid BST.
  • Change the values in place; the shape of the tree must not change.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (collect, sort, write back)O(n log n)O(n)
Better (in-order with a previous pointer)O(n)O(h)
Optimal (Morris in-order traversal)O(n)O(1)

1Brute force (collect, sort, write back)

TimeO(n log n)Sorting the n values dominates; the two walks are linear.
SpaceO(n)The list of values plus the recursion stack.

Read all values with an in-order walk, sort them, then do a second in-order walk that writes the sorted values back node by node. The result is the only BST with this shape and these values, so the two swapped nodes end up fixed.

  1. In-order walk: append every value to a list.
  2. Sort the list.
  3. In-order walk again, assigning list[i++] to each node.
class Solution {
    private List<Integer> vals = new ArrayList<>();
    private int idx = 0;

    public void recoverTree(TreeNode root) {
        collect(root);
        Collections.sort(vals);
        idx = 0;
        write(root);
    }

    private void collect(TreeNode node) {
        if (node == null) return;
        collect(node.left);
        vals.add(node.val);
        collect(node.right);
    }

    private void write(TreeNode node) {
        if (node == null) return;
        write(node.left);
        node.val = vals.get(idx++);
        write(node.right);
    }
}

2Better (in-order with a previous pointer)

TimeO(n)Every node is visited once.
SpaceO(h)The recursion stack is as deep as the tree height h (n for a chain).

Walk the tree in order, remembering the previously visited node. Whenever prev.val > cur.val there is a drop. At the first drop the misplaced larger value is prev; at every drop the smaller value is cur, so after the walk the second node is the cur of the last drop. Swap the two values.

  1. first = second = prev = null.
  2. Recursive in-order: at each node, if prev != null and prev.val > node.val: if first is null set first = prev; set second = node.
  3. Set prev = node and continue.
  4. Swap first.val and second.val.
class Solution {
    private TreeNode first, second, prev;

    public void recoverTree(TreeNode root) {
        first = second = prev = null;
        inorder(root);
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }

    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;
        }
        prev = node;
        inorder(node.right);
    }
}

3Optimal (Morris in-order traversal)

TimeO(n)Each edge is walked at most a constant number of times while threads are created and removed.
SpaceO(1)Only a few pointers; the temporary threads reuse existing null right pointers.

Do the same drop detection, but walk in order with Morris threading instead of recursion. For a node with a left subtree, find its in-order predecessor (rightmost node of the left subtree). If the predecessor's right pointer is empty, point it back at the node and go left; if it already points at the node, remove the thread, visit the node and go right. Every node is visited in sorted position with O(1) extra memory, and the tree is restored to its original shape.

  1. cur = root. While cur != null:
  2. If cur.left is null: visit cur, cur = cur.right.
  3. Else find pred = rightmost of cur.left (stopping if pred.right == cur). If pred.right is null: set pred.right = cur, cur = cur.left. Otherwise set pred.right = null, visit cur, cur = cur.right.
  4. Visiting compares with prev exactly as in the previous approach. Finally swap first.val and second.val.
class Solution {
    public void recoverTree(TreeNode root) {
        TreeNode first = null, second = null, prev = null, cur = root;
        while (cur != null) {
            if (cur.left != null) {
                TreeNode pred = cur.left;
                while (pred.right != null && pred.right != cur) pred = pred.right;
                if (pred.right == null) {
                    pred.right = cur;
                    cur = cur.left;
                    continue;
                }
                pred.right = null;
            }
            if (prev != null && prev.val > cur.val) {
                if (first == null) first = prev;
                second = cur;
            }
            prev = cur;
            cur = cur.right;
        }
        int tmp = first.val;
        first.val = second.val;
        second.val = tmp;
    }
}

Edge cases to test

  • The two swapped nodes are neighbours in in-order (only one descent in the sequence)
  • The root is one of the swapped nodes
  • A two-node tree
  • A completely skewed tree (a chain)
  • Values at the ends of the int range

Hints

Hint 1

An in-order walk of a valid BST lists the values in increasing order. What does swapping two values do to that sorted sequence?

Hint 2

Look for places where a value is larger than the one after it. There are either two such drops or just one (when the swapped nodes are adjacent in the sequence).

Hint 3

The first wrong node is the larger value at the first drop; the second is the smaller value at the last drop. Morris traversal lets you walk in order without a stack, for O(1) extra space.

FAQ

What is the best time complexity for Recover Binary Search Tree?

Optimal (Morris in-order traversal) runs in O(n) time and O(1) extra space. Each edge is walked at most a constant number of times while threads are created and removed.

Which pattern does Recover Binary Search Tree use?

It is a trees & bst problem that uses the bst basics pattern. Other problems with the same pattern: Search in a Binary Search Tree, Minimum element in BST, Insert into a Binary Search Tree.

Is there a brute force solution for Recover Binary Search Tree?

Yes. Brute force (collect, sort, write back) takes O(n log n) time and O(n) space. Read all values with an in-order walk, sort them, then do a second in-order walk that writes the sorted values back node by node.

Which edge cases should I test for Recover Binary Search Tree?

The two swapped nodes are neighbours in in-order (only one descent in the sequence); The root is one of the swapped nodes; A two-node tree; A completely skewed tree (a chain); Values at the ends of the int range.