99. Recover Binary Search Tree LeetCode Solution

In this guide, you will get 99. Recover Binary Search Tree LeetCode Solution with the best time and space complexity. The solution to Recover Binary Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Recover Binary Search Tree solution in C++
Recover Binary Search Tree solution in Java
Recover Binary Search Tree solution in Python
Additional Resources

99. Recover Binary Search Tree LeetCode Solution image

Problem Statement of Recover Binary Search Tree

You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure.

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

Follow up: A solution using O(n) space is pretty straight-forward. Could you devise a constant O(1) space solution?

Complexity Analysis

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

99. Recover Binary Search Tree LeetCode Solution in C++

class Solution {
 public:
  void recoverTree(TreeNode* root) {
    inorder(root);
    swap(x, y);
  }

 private:
  TreeNode* pred = nullptr;
  TreeNode* x = nullptr;  // the first wrong node
  TreeNode* y = nullptr;  // the second wrong node

  void inorder(TreeNode* root) {
    if (root == nullptr)
      return;

    inorder(root->left);

    if (pred && root->val < pred->val) {
      y = root;
      if (x == nullptr)
        x = pred;
      else
        return;
    }
    pred = root;

    inorder(root->right);
  }

  void swap(TreeNode* x, TreeNode* y) {
    const int temp = x->val;
    x->val = y->val;
    y->val = temp;
  }
};
/* code provided by PROGIEZ */

99. Recover Binary Search Tree LeetCode Solution in Java

class Solution {
  public void recoverTree(TreeNode root) {
    inorder(root);
    swap(x, y);
  }

  private TreeNode pred = null;
  private TreeNode x = null; // the first wrong node
  private TreeNode y = null; // the second wrong node

  private void inorder(TreeNode root) {
    if (root == null)
      return;

    inorder(root.left);

    if (pred != null && root.val < pred.val) {
      y = root;
      if (x == null)
        x = pred;
      else
        return;
    }
    pred = root;

    inorder(root.right);
  }

  private void swap(TreeNode x, TreeNode y) {
    final int temp = x.val;
    x.val = y.val;
    y.val = temp;
  }
}
// code provided by PROGIEZ

99. Recover Binary Search Tree LeetCode Solution in Python

class Solution:
  def recoverTree(self, root: TreeNode | None) -> None:
    def swap(x: TreeNode | None, y: TreeNode | None) -> None:
      temp = x.val
      x.val = y.val
      y.val = temp

    def inorder(root: TreeNode | None) -> None:
      if not root:
        return

      inorder(root.left)

      if self.pred and root.val < self.pred.val:
        self.y = root
        if not self.x:
          self.x = self.pred
        else:
          return
      self.pred = root

      inorder(root.right)

    inorder(root)
    swap(self.x, self.y)

  pred = None
  x = None  # the first wrong node
  y = None  # the second wrong node
 # code by PROGIEZ