# [recommend for beginners]clean C++ implementation with detailed explaination

• Just use the "first" and "second" pointer to find the 2 nodes that violate the order. Then change the value of the first node ad the second node by their value.

``````class Solution {
TreeNode* first=NULL;
TreeNode* second=NULL;
TreeNode* prev = new TreeNode(INT_MIN);
public:
void recoverTree(TreeNode* root) {
help(root);
swp(first->val, second->val);
}

void help(TreeNode* root){
if(root==NULL)  return;
help(root->left);
if(first==NULL && prev->val >= root->val)   first=prev;
if(first!=NULL && prev->val >= root->val)   second=root;
prev=root;
help(root->right);
}
};``````

• I have a question... Is recursion considered as constant space?

• I have the same question, and I think the space complexity is O(log(n)) if recursion is used.

• ``````class Solution {
TreeNode* first = nullptr;
TreeNode* second = nullptr;
TreeNode* prev = new TreeNode(INT_MIN);
public:
void recoverTree(TreeNode* root) {
help(root);
swap(first->val, second->val);
}

void help(TreeNode* root) {
if (!root) return;
help(root->left);
if (first == nullptr && prev->val >= root->val) first = prev;
if (first != nullptr && prev->val >= root->val) second = root;
prev = root;
help(root->right);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.