Recover Binary Search Tree Medium 0 attempts
LeetCode ↗

Recover Binary Search Tree

Medium TreeBinary TreeDFS LeetCode

A binary search tree had exactly two of its nodes accidentally swapped. Fix the tree back to a valid BST without altering its overall structure.

Input Format
Implement recoverTree(root). Inputs below show JavaScript function arguments; there is no stdin parsing. Trees use level-order arrays with null for missing children. The editor passes nodes with val, left, and right properties; [] becomes null.
Output Format
Modify argument 1 in place. The editor compares its final value; the function return value is ignored. Returned trees are displayed as level-order arrays, trimming trailing nulls.

Sample Input and Output

Example 1 ยท Run Sample

Input
root = [1,3,null,null,2]
Output
[3,1,null,null,2]

Example 2

Input
root = [3,1,4,null,null,2]
Output
[2,1,4,null,null,3]
Constraints
  • 2 <= number of nodes <= 1000
  • -2^31 <= Node.val <= 2^31 - 1
Test Cases (2)
Case 1
Args: [[1,3,null,null,2]] Expected: [3,1,null,null,2]
Case 2
Args: [[3,1,4,null,null,2]] Expected: [2,1,4,null,null,3]
Topics
TreeBinary TreeDFS

Recursive Inorder Traversal

Find two nodes where inorder sequence is violated.

javascript
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.

JavaScript