0099. Recover Binary Search Tree

You are given the root of a binary search tree (BST), where 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 space solution?

Example 1:

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

Constraints:

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

Analysis

Using in-order tree traversal, we can find that all the left < root > right. If there are any invalid nodes, we should find left(prev) > root. We keep track of last level's root as prev where current root is its left child.

There are two situations: 1. first isn't populated, so the first two nodes to be swapped are prev and root. 2. first is populated, then we traverse all the way down to find the last prev that is greater than root.

Time Complexity: $O(n)$ as it's an in-order traversal Space Complexity: $O(n)$, in the worst case the tree is a linked list

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left),
 * right(right) {}
 * };
 */
class Solution {
 public:
  TreeNode* first = NULL;
  TreeNode* second = NULL;
  TreeNode* prev = new TreeNode(INT_MIN);
  void recoverTree(TreeNode* root) {
    help(root);
    swap(first->val, second->val);
  }

  void help(TreeNode* root) {
    if (root == NULL) return;
    help(root->left);
    if (first == NULL && prev->val > root->val) first = prev;
    if (first != NULL && prev->val > root->val) second = root;
    prev = root;
    help(root->right);
  }