Recover Binary Search Tree | Problems

Two nodes of a BST are swapped by mistake. Recover the tree without changing its structure.

Example: root = [1,3,null,null,2] → [3,1,null,null,2]

Sample Input

—

Sample Output

—

Constraints

2 <= number of nodes <= 1000
-2^31 <= Node.val <= 2^31 - 1

Topics

Tree Binary Tree DFS

Morris Inorder / Stack Inorder

Find two nodes where inorder sequence is violated.

function recoverTree(root) {
  let first = null, second = null, prev = {val: -Infinity};
  function inorder(node) {
    if (!node) return;
    inorder(node.left);
    if (node.val < prev.val) {
      if (!first) first = prev;
      second = node;
    }
    prev = node;
    inorder(node.right);
  }
  inorder(root);
  [first.val, second.val] = [second.val, first.val];
}

Time: O(n) | Space: O(h)

Saved in this browser only. Private to you.