# StraightForward, O(N) Function stack, C++ Solution

• The key is to keey a previous TreeNode,
Since it's a BST, inorder traversal gives us a sorted order. Whenever we finish visiting a node, we update the prev TreeNode

goLeft

root, update(prev)

goRight

``````void recoverTree(TreeNode* root)
{
if(root == NULL)
return;
TreeNode* node1 = NULL, *node2 = NULL, *previous = NULL;

traverse(root, parent, node1, node2);
if(node1!=NULL && node2!=NULL)
{
int tmp = node1->val;
node1->val = node2->val;
node2->val = tmp;
}
}

void traverse(TreeNode* root, TreeNode* & previous, TreeNode* & node1, TreeNode* & node2)
{
if(root == NULL)
return;

traverse(root->left, previous, node1, node2);
int val = root->val;

if(previous != NULL)
{
if( previous->val > root->val )
{
if(node1 == NULL)
{
node1 = previous;
node2 = root;
}
else
node2 = root;
}
}
previous = root;
traverse(root->right, previous, node1, node2);
}``````

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