Recover Binary Search Tree

07/11/2016 Tree Depth First Search

Question
Solution

Question

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note:

A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

Solution

Result: Accepted Time: 48 ms

Here should be some explanations.

class Solution {
public:
    void inorder(TreeNode * root,TreeNode * data[],int &ptr,int &last)
    {
        if(root == NULL) return ;
        inorder(root->left,data,ptr,last);
        if(last > root->val)
            ptr++;
        if(ptr == 0)
            data[ptr] = root;
        else if(data[0]->val > root->val)
        {
            if(ptr >= 2 && data[1]->val > root->val)
                data[1] = root;
            if(ptr == 1)
                data[ptr] = root;
        }
        last = root->val;
        inorder(root->right,data,ptr,last);
    }

    void recoverTree(TreeNode* root) {
        TreeNode * data[2]={0};
        int last = INT_MIN,ptr = 0;
        inorder(root,data,ptr,last);
        if(data[1])
            swap(data[0]->val,data[1]->val);
    }
};

Complexity Analytics

Time Complexity: $O(n)$
Space Complexity: $O(1)$