algoadvance

Leetcode 99. Recover Binary Search Tree

Problem Statement

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.

Clarifying Questions

  1. What are the constraints on the tree?
    • The number of nodes in the tree is in the range [2, 1000].
    • -2^31 <= Node.val <= 2^31 - 1
  2. Can the input tree be null?
    • No, the problem specifies that there are at least two nodes in the tree.
  3. Do we need to maintain the same tree structure or can it be rearranged?
    • We need to recover the tree without changing its structure.
  4. Is it guaranteed that there is exactly one pair of nodes that has been swapped?
    • Yes, the problem guarantees that exactly two nodes are swapped.

Now, let’s outline the strategy.

Strategy

1. Inorder Traversal to Detect Swapped Nodes:

2. Swapping the Nodes:

Steps

  1. Perform an inorder traversal and keep track of the previous node.
  2. Identify the two nodes that violate the BST properties (appear in the wrong order).
  3. Swap the values of these two nodes.

Code

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) { 
        this.val = val; 
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    private TreeNode firstElement = null;
    private TreeNode secondElement = null;
    private TreeNode prevElement = new TreeNode(Integer.MIN_VALUE);
    
    public void recoverTree(TreeNode root) {
        // Use inorder traversal to find the two nodes that are swapped by mistake
        traverse(root);
        
        // Swap the values of the two nodes
        int temp = firstElement.val;
        firstElement.val = secondElement.val;
        secondElement.val = temp;
    }
    
    private void traverse(TreeNode root) {
        if (root == null) {
            return;
        }
        
        // Traversal the left subtree
        traverse(root.left);
        
        // Start identifying out of order elements
        if (firstElement == null && prevElement.val >= root.val) {
            firstElement = prevElement;
        }
        
        if (firstElement != null && prevElement.val >= root.val) {
            secondElement = root;
        }
        
        // Update previous element to current root
        prevElement = root;
        
        // Traversal the right subtree
        traverse(root.right);
    }
}

Time Complexity

The time complexity for this solution is O(n) where n is the number of nodes in the tree. This is because we visit each node exactly once during the inorder traversal.

Space Complexity

The space complexity is O(h), where h is the height of the tree. This is the space used by the recursion stack during the traversal. In the worst case of a completely unbalanced tree, this can be O(n). In the best case of a balanced tree, it is O(log n).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI