## DEV Community # 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 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.

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 BST 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.

Turns our if you combine Depth First Search In-Order traversal to a Binary Search Tree, it should present you an array of values in sorted order. Once I figured this out I was able to solve this problem.

## What do we know?

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

## 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 NEXT node we visit should always be greater than the previous node. If it isn't, then we know that we have found one of the swapped nodes.

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) | Where n is the number of nodes in our Binary Search Tree | As we're going to traverse all of the nodes within the tree.
• Space Complexity: O(h) | Where h is the height of the Binary Search Tree | Because we're going to store the height of the tree within the Call Stack due to the in-order traversal.

'Could this be improved?' Yes! Morris Traversal could do this problem in O(1) space complexity. But Morris Traversal is tricky and tough to read. For the sake of simplicity, I don't use it here.

## Leetcode Results:

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

``````var recoverTree = function (root) {

/* -------------------------------------------------------------------------- */
/*                       99. Recover Binary Search Tree                       */
/* -------------------------------------------------------------------------- */

/**
* @author  Samuel Hinchliffe
*/

/* ----------------------------- Solution Below ----------------------------- */

// Our bad nodes (We will swap them later)

// 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

// 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.
}

// 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
}

// Update our prev_nodes node pointer
prev_node = node;

// Get all the right nodes
};

// We have found the bad nodes, now swap them

// Swap the values of the bad nodes
};

`````` Samuel Hinchliffe 🚀

# 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 clarity on a certain section of it. Please do not hesitate to contact me. We're all in this together and I'm happy to help. 😁