• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
void recoverTree(TreeNode* root) {
inorder(root);
swap(x, y);
}

private:
TreeNode* pred = nullptr;
TreeNode* x = nullptr;  // 1st wrong node
TreeNode* y = nullptr;  // 2nd wrond node

void inorder(TreeNode* root) {
if (!root)
return;

inorder(root->left);

if (pred && root->val < pred->val) {
y = root;
if (!x)
x = pred;
else
return;
}
pred = root;

inorder(root->right);
}

void swap(TreeNode* x, TreeNode* y) {
const int temp = x->val;
x->val = y->val;
y->val = temp;
}
};
``````

## JAVA

``````class Solution {
public void recoverTree(TreeNode root) {
inorder(root);
swap(x, y);
}

private TreeNode pred = null;
private TreeNode x = null;
private TreeNode y = null;

private void inorder(TreeNode root) {
if (root == null)
return;

inorder(root.left);

if (pred != null && root.val < pred.val) {
y = root;
if (x == null)
x = pred;
else
return;
}
pred = root;

inorder(root.right);
}

private void swap(TreeNode x, TreeNode y) {
final int temp = x.val;
x.val = y.val;
y.val = temp;
}
}
``````

## Python

``````class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
def swap(x: Optional[TreeNode], y: Optional[TreeNode]) -> None:
temp = x.val
x.val = y.val
y.val = temp

def inorder(root: Optional[TreeNode]) -> None:
if not root:
return

inorder(root.left)

if self.pred and root.val < self.pred.val:
self.y = root
if not self.x:
self.x = self.pred
else:
return
self.pred = root

inorder(root.right)

inorder(root)
swap(self.x, self.y)

pred = None
x = None  # 1st wrong node
y = None  # 2nd wrong node
``````

• Time:O(n)
• Space:O(h)

## C++

``````class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* pred = nullptr;
TreeNode* x = nullptr;  // 1st wrong node
TreeNode* y = nullptr;  // 2nd wrong node

stack<TreeNode*> stack;

while (root || !stack.empty()) {
while (root) {
stack.push(root);
root = root->left;
}
root = stack.top(), stack.pop();
if (pred && root->val < pred->val) {
y = root;
if (!x)
x = pred;
}
pred = root;
root = root->right;
}

swap(x, y);
}

void swap(TreeNode* x, TreeNode* y) {
const int temp = x->val;
x->val = y->val;
y->val = temp;
}
};
``````

## JAVA

``````class Solution {
public void recoverTree(TreeNode root) {
TreeNode pred = null;
TreeNode x = null;
TreeNode y = null;

Deque<TreeNode> stack = new ArrayDeque<>();

while (root != null || !stack.isEmpty()) {
while (root != null) {
root = root.left;
}
root = stack.pollLast();
if (pred != null && root.val < pred.val) {
y = root;
if (x == null)
x = pred;
}
pred = root;
root = root.right;
}

swap(x, y);
}

private void swap(TreeNode x, TreeNode y) {
final int temp = x.val;
x.val = y.val;
y.val = temp;
}
}
``````

## Python

``````class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
pred = None
x = None  # 1st wrong node
y = None  # 2nd wrong node
stack = []

while root or stack:
while root:
stack.append(root)
root = root.left
root = stack.pop()
if pred and root.val < pred.val:
y = root
if not x:
x = pred
pred = root
root = root.right

def swap(x: Optional[TreeNode], y: Optional[TreeNode]) -> None:
temp = x.val
x.val = y.val
y.val = temp

swap(x, y)
``````

• Time:O(n)
• Space:O(1)

## C++

``````class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode* pred = nullptr;
TreeNode* x = nullptr;  // 1st wrong node
TreeNode* y = nullptr;  // 2nd wrong node

while (root) {
if (root->left) {
TreeNode* morrisPred = findPredecessor(root);
if (morrisPred->right) {  // already connected before
visit(root, pred, x, y);
morrisPred->right = nullptr;  // break the connection
root = root->right;
} else {
morrisPred->right = root;  // connect it!
root = root->left;
}
} else {
visit(root, pred, x, y);
root = root->right;
}
}

swap(x, y);
}

private:
TreeNode* findPredecessor(TreeNode* root) {
TreeNode* pred = root->left;
while (pred->right && pred->right != root)
pred = pred->right;
return pred;
}

void visit(TreeNode*& root, TreeNode*& pred, TreeNode*& x, TreeNode*& y) {
if (pred && root->val < pred->val) {
y = root;
if (!x)
x = pred;
}
pred = root;
}

void swap(TreeNode* x, TreeNode* y) {
const int temp = x->val;
x->val = y->val;
y->val = temp;
}
};
``````

## JAVA

``````class Solution {
public void recoverTree(TreeNode root) {
TreeNode pred = null;
TreeNode x = null; // 1st wrong node
TreeNode y = null; // 2nd wrong node

while (root != null) {
if (root.left == null) {
// start the main logic
if (pred != null && root.val < pred.val) {
y = root;
if (x == null)
x = pred;
}
pred = root;
// end of the main logic
root = root.right;
} else {
TreeNode morrisPred = findPredecessor(root);
if (morrisPred.right == null) {
morrisPred.right = root; // connect it!
root = root.left;
} else { // already connected before
// start the main logic
if (pred != null && root.val < pred.val) {
y = root;
if (x == null)
x = pred;
}
pred = root;
// end of the main logic
morrisPred.right = null; // break the connection
root = root.right;
}
}
}

swap(x, y);
}

private TreeNode findPredecessor(TreeNode root) {
TreeNode pred = root.left;
while (pred.right != null && pred.right != root)
pred = pred.right;
return pred;
}

private void swap(TreeNode x, TreeNode y) {
final int temp = x.val;
x.val = y.val;
y.val = temp;
}
}
``````

## Python

``````class Solution:
def recoverTree(self, root: Optional[TreeNode]) -> None:
pred = None
x = None  # 1st wrong node
y = None  # 2nd wrong node

def findPredecessor(root: Optional[TreeNode]) -> Optional[TreeNode]:
pred = root.left
while pred.right and pred.right != root:
pred = pred.right
return pred

while root:
if root.left:
morrisPred = findPredecessor(root)
if morrisPred.right:  # already connected before
# start the main logic
if pred and root.val < pred.val:
y = root
if not x:
x = pred
pred = root
# end of the main logic
morrisPred.right = None  # break the connection
root = root.right
else:
morrisPred.right = root  # connect it!
root = root.left
else:
# start the main logic
if pred and root.val < pred.val:
y = root
if not x:
x = pred
pred = root
# end of the main logic
root = root.right

def swap(x: Optional[TreeNode], y: Optional[TreeNode]) -> None:
temp = x.val
x.val = y.val
y.val = temp

swap(x, y)
``````