99. Recover Binary Search Tree 🚀
Tags: javascript, leetcode, tutorial, programming
Published: 2022-04-26 15:16:29

# 99. Recover Binary Search Tree 🚀
***
### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
We will be covering Leetcode '[99. Recover Binary Search Tree](https://leetcode.com/problems/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.

##  Recommended Knowledge
1. [Binary Tree](https://en.wikipedia.org/wiki/Binary_tree)
2. [Depth First Search](https://en.wikipedia.org/wiki/Depth-first_search)
3. [In-order traversal](https://en.wikipedia.org/wiki/Tree_traversal#In-order)
4. [Binary Search Tree](https://en.wikipedia.org/wiki/Binary_search_tree)

## 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](https://en.wikipedia.org/wiki/Call_stack) due to the [in-order traversal](https://en.wikipedia.org/wiki/Tree_traversal#In-order).

'***Could this be improved?***' Yes! [Morris Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Morris_traversal) could do this problem in ***O(1) space complexity***. But [Morris Traversal](https://en.wikipedia.org/wiki/Tree_traversal#Morris_traversal) is tricky and tough to read. For the sake of simplicity, I don't use it here. 

## Leetcode Results:

See Submission Link: 

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

[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/687918635/)


***

# 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;
};

```