Problem Statement

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.

Examples

Example 1:

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

Explanation: 3 cannot be a left child of 1 as it is bigger than 1 (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.

Different Approaches

1️⃣ Brute Force Approach

Intuition:

To fix a BST with two swapped nodes, the key is to recognize that an inorder traversal of a BST yields a sorted sequence. First, collect the node values using an inorder traversal, which will provide an array of values. Sorting this array reveals what the inorder sequence should be if the BST were correct. By comparing the BST's actual inorder traversal with this sorted array, it's possible to identify where the nodes are out of order. The task then is to correct these discrepancies by updating the BST nodes with the appropriate values from the sorted array, thereby restoring the BST's correct structure without altering its overall form.

Approach:

1. Perform an inorder traversal of the BST to gather the node values into an array. Sort this array to get the correct inorder sequence of the BST.
2. Traverse the BST again using inorder traversal, comparing each node's value with the corresponding value in the sorted array.
3. When a mismatch is found between a node's value and the value from the sorted array, update the BST node with the correct value from the sorted array.
4. Return the modified BST.

Code:

#include <bits/stdc++.h>
using namespace std;

/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    void recoverTree(TreeNode* root) {
        // Step 1: Collect node values via inorder traversal
        collectInorder(root);

        // Step 2: Sort the values to get correct inorder sequence
        sort(inorderValues.begin(), inorderValues.end());

        // Step 3: Traverse again and assign sorted values back
        restoreInorder(root);
    }
    
private:
    // Vector to hold inorder traversal values
    vector<int> inorderValues;
    int index = 0;

    /* First traversal: Collect values in inorder */
    void collectInorder(TreeNode* root) {
        if (!root) return;
        collectInorder(root->left);
        inorderValues.push_back(root->data);
        collectInorder(root->right);
    }

    /* Second traversal: Replace node values with sorted values */
    void restoreInorder(TreeNode* root) {
        if (!root) return;
        restoreInorder(root->left);
        root->data = inorderValues[index++];
        restoreInorder(root->right);
    }
};

// Helper function to insert nodes in the tree for testing purposes
TreeNode* insertLevelOrder(vector<int>& arr, int i) {
    if (i >= arr.size() || arr[i] == -1) return nullptr;
    TreeNode* root = new TreeNode(arr[i]);
    root->left = insertLevelOrder(arr, 2 * i + 1);
    root->right = insertLevelOrder(arr, 2 * i + 2);
    return root;
}

// Helper function to print inorder traversal of the tree
void inorderPrint(TreeNode* root) {
    if (root) {
        inorderPrint(root->left);
        cout << root->data << " ";
        inorderPrint(root->right);
    }
}

int main() {
    // Example input tree: [1, 3, -1, -1, 2]
    vector<int> nodes = {1, 3, -1, -1, 2};
    TreeNode* root = insertLevelOrder(nodes, 0);

    // Solution instance
    Solution sol;
    sol.recoverTree(root);

    // Print corrected tree
    inorderPrint(root);

    return 0;
}

Complexity Analysis:

• Time Complexity:O(N*logN), where N is the number of nodes in the tree.
  • The inorder traversal takes O(N) time. Sorting the inorder traversal takes O(N*logN) time. Traversing the tree again to correct it will take another O(N) time. Hence, the total complexity becomes O(2N + N*logN) or simply O(N*logN).
• Space Complexity:O(N)
  • Storing the inorder traversal takes O(N) space and the recursive stack space required to compute the inorder traversal recursively is O(H), where H is the height of the tree. In worst cases (in case of skew tree), H is equivalent to N. Hence, the overall space complexity becomes O(N) + O(H) or simply O(N).