Recover Binary Search Tree is an example of tree problems. In this post we will see how we can solve in Javascript.

Problem Description

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?

The idea is simple, find the two nodes that are swapped by mistake and then swap back their values. The question is how to find out those two nodes?

As we know, an inorder traversal of BST gives us a sorted array, if two elements in the array are swapped, we can find them out in one scan, that is whenever we see the previous value is larger than the current value, we can mark them.

Example 1

Let's say we have a sorted array [0, 1] and we swap the values, so that array becomes [1, 0], when we scan through, we found that 1 > 0, we know that 1 and 0 are the nodes that are swapped by mistake.

Example 2

In this array [0, 1, 2, 5, 4, 3], 3 and 5 are swapped by mistake, when we scan the array, we noticed that 5 > 4 and 4 > 3. How to get 3 and 5? Whenever we find a mistake, if it's the first one, mark both nodes as "first" and "second", for the second mistake, we just have to update the "second", see the codes below.

Complexity

But we are not there yet, the question asks us to use constant space, so we can't store the values of the BST in an array, that will be O(n) space complexity. The solution is to use DFS and traverse the tree in inorder manner.

So time complexity is O(n), space complexity is O(1) (if we don't care about recursion stack, otherwise it's the height of the tree).

Solution: Please check the main.js snippet for the solution. If you have different approach in mind or have any suggestion for this implementation feel free to share in the comment below. Thanks!