# 99. Recover Binary Search Tree π

### Solution Developed In:

## The Question

We will be covering Leetcode '99. Recover Binary Search Tree' question. This question is rated as a **Medium** question.

Question:

You are given the

`root`

of a(BST), where the values of exactly twobinary search tree`nodes`

of the tree were swapped by mistake. Recover the tree without changing its structure.

Example:

```
Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.
```

## Explaining The Question

This Question is rated **Medium**. While I don't think its a **Hard** question. It's certainly not a **Easy** question and it's certainly not your average ** Medium** question either.

I say this because I was ** stuck on this question for a few days** (Even with the pseudocode solutions). Multiple attempts later to solve this question proved failure for me.

I don't think I understood ** Binary Search Trees** well enough to understand the question. I was given a

**and I was told that two nodes were swapped. I was told that I could swap the values of the nodes and then the tree would be valid. But I honestly didn't understand how you could detect 2 invalid nodes and then swap them back.**

*BST*Turns our if you combine ** Depth First Search In-Order traversal** to a

**, it should present you an array of values in**

*Binary Search Tree***sorted order**. Once I figured this out I was able to solve this problem.

## Recommended Knowledge

## What do we know?

- We have been given a
that is broken.*Binary Search Tree* - We know that 2 of the nodes in the
are swapped.*Binary Search Tree* - We know that we can swap the values of the nodes and then the tree would be valid.
- We know that we can use
to a*Depth First Search In-Order traversal*to get an array of values in sorted order.*Binary Search Tree*

## How we're going to do it:

Basically, what we're going to do is to traverse the Binary Tree in ** In-Order**. What this mean's is that the

**node we visit should always be**

*NEXT***than the previous node. If it isn't, then we know that we have found one of the swapped nodes.**

*greater*Once we detect that ** first swapped node**, we store it in a variable called

`bad_node_1`

. Now all we have to do is find that second bad node and swap it. So we apply the same logic as before, comparing the next node to the previous nodes value to see if it's greater or less than the previous node. If we detect that the current node is less than the previous node, then we know that we have found the second bad node. We will then store it in a variable called `bad_node_2`

.Then simply swap their `values`

. This is the end of our logic.

## Big O Notation:

- Time Complexity:
*O(**n**)*| Whereis the number of nodes in our*n*| As we're going to traverse all of the nodes within the tree.*Binary Search Tree* - Space Complexity:
*O(**h**)*| Whereis the height of the*h*| Because we're going to store the height of the tree within the Call Stack due to the in-order traversal.*Binary Search Tree*

'** Could this be improved?**' Yes! Morris Traversal could do this problem in

**. But Morris Traversal is tricky and tough to read. For the sake of simplicity, I don't use it here.**

*O(1) space complexity*## Leetcode Results:

See Submission Link:

- Runtime: 128 ms, faster than
of JavaScript online submissions for Recover Binary Search Tree.*96.39%* - Memory Usage: 52.8 MB, less than
of JavaScript online submissions for Recover Binary Search Tree.*12.17%*

# The Solution

```
var recoverTree = function (root) {
/* -------------------------------------------------------------------------- */
/* 99. Recover Binary Search Tree */
/* -------------------------------------------------------------------------- */
/**
* @author Samuel Hinchliffe
* @see {@link linkedin.com/in/samuel-hinchliffe-π-2bb5801a5/ | Author's Linkedin }
* @see {@link github.com/Samuel-Hinchliffe}
*/
/* ----------------------------- Solution Below ----------------------------- */
// Our bad nodes (We will swap them later)
let bad_node_1 = null;
let bad_node_2 = null;
// A prev_node node to help us keep track of
// the last node we visited.
// We set it as a dummy node
let prev_node = new TreeNode(-Infinity, null, null);
// The function that will find the 2 bad nodes
const find_bad_nodes = (node) => {
// Reached end of tree
if (!node) {
return null;
}
/* --------------- Perform In-Order Traversal --------------- */
// Get all the left nodes
find_bad_nodes(node.left);
// Is the node less than the prev_node val?
// And have we set bad_node_1 yet?
if (bad_node_1 == null && prev_node.val >= node.val) {
// Set the bad node to be the one behind it.
bad_node_1 = prev_node;
}
// Is the node less than the prev_node val?
// and have we set bad_node_1 yet?
if (bad_node_1 != null && prev_node.val >= node.val) {
// Set the bad node to the current node
bad_node_2 = node;
}
// Update our prev_nodes node pointer
prev_node = node;
// Get all the right nodes
find_bad_nodes(node.right);
};
// FIND THOSE BAD NODES!!!
find_bad_nodes(root, prev_node);
// We have found the bad nodes, now swap them
// Swap the values of the bad nodes
let temp = bad_node_1.val;
bad_node_1.val = bad_node_2.val;
bad_node_2.val = temp;
};
```

## Top comments (1)

## Hey There π

Thank you for taking the time to look at my solution. I hope you found it interesting and useful.

If you're having difficulties understanding this solution or just need some

on a certain section of it. Please do not hesitate to contact me. We're all in this together and I'm happy toclarity. πhelp## Contact me here: