algoadvance

Leetcode 99. Recover Binary Search Tree Sure, let’s tackle the problem “99. Recover Binary Search Tree.”

Problem Statement

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

Clarifying Questions

  1. Are there any constraints on the size of the tree?
    • No specific constraints besides typical memory and performance considerations.
  2. Can we assume that there will always be exactly two nodes swapped?
    • Yes, the problem guarantees that exactly two nodes have been swapped.
  3. What should we return from our function?
    • We need to modify the tree in place, so no return is necessary.

Strategy

The main idea is to use the in-order traversal of the BST, which should yield a sorted list of values. When two nodes are swapped, the in-order traversal will not be sorted correctly. By identifying the points where the order is violated, we can pinpoint the two nodes that have been swapped.

  1. Perform an in-order traversal to find the two nodes. During traversal:
    • First node (first) is identified when we find the first pair where a previous node has a larger value than the current node.
    • Second node (second) is identified when we find the second pair where a previous node has a larger value than the current node (or if we only find one pair, then it must involve first and second directly).
  2. Swap the values of the two nodes identified.

Code

#include <iostream>

// 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:
    void recoverTree(TreeNode* root) {
        TreeNode *first = nullptr, *second = nullptr, *prev = nullptr;

        // Helper function for the modified in-order traversal
        std::function<void(TreeNode*)> inorder = [&](TreeNode* node) {
            if (!node) return;

            inorder(node->left); // Traverse the left subtree

            // Check for swapped nodes
            if (prev && prev->val > node->val) {
                if (!first) first = prev;
                second = node;
            }
            prev = node;

            inorder(node->right); // Traverse the right subtree
        };

        inorder(root);

        // Swap values of the two identified nodes
        if (first && second) {
            std::swap(first->val, second->val);
        }
    }
};

// Function for testing the code 
void inorderPrint(TreeNode* root) {
    if (!root) return;
    inorderPrint(root->left);
    std::cout << root->val << " ";
    inorderPrint(root->right);
}

int main() {
    // Example usage
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(3);
    root->left->right = new TreeNode(2);

    std::cout << "Before recover: ";
    inorderPrint(root);
    std::cout << std::endl;

    Solution().recoverTree(root);

    std::cout << "After recover: ";
    inorderPrint(root);
    std::cout << std::endl;

    // Clean up the tree (not strictly necessary in a problem setting)
    delete root->left->right;
    delete root->left;
    delete root;

    return 0;
}

Time Complexity

The time complexity of this approach is O(N) where N is the number of nodes in the tree. This is because we traverse each node once during the in-order traversal.

Space Complexity

The space complexity is O(H), where H is the height of the tree. In the case of a balanced tree, this is O(log N), but in the worst case (a completely unbalanced tree), it is O(N). This space is used for the recursion stack during the in-order traversal.

This solution effectively solves the problem by making use of the properties of in-order traversal and BST. The identified swapped nodes are corrected by simply swapping their values.

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