# Recover Binary Search Tree

You are 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*.

```
class Solution {
TreeNode prev = null, first = null, second = null;
public void recoverTree(TreeNode root) {
evalSwappedNodes(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
private void evalSwappedNodes(TreeNode curr) {
if (curr == null)
return;
evalSwappedNodes(curr.left);
if (prev != null && prev.val > curr.val) {
if (first == null)
first = prev;
second = curr;
}
prev = curr;
evalSwappedNodes(curr.right);
}
}
```

## Related Problems

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists into one **sorted** list. The list should be made by splicing together the nodes of the first two lists.

Return *the head of the merged linked list*.

Given the root of a binary tree, flatten the tree into a "linked list":

The "linked list" should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The "linked list" should be in the same order as a pre-order traversal of the binary tree.

You are given two binary trees root1 and root2.

Imagine the trees are layed ontop of each other. The merged nodes will have the sum of the values of the original nodes. If one or the other is null, treat the null node as if it had a value of 0.

Return *the merged tree*.

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return *the binary tree*.