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.

Recommended Knowledge

1. Binary Tree
2. Depth First Search
3. In-order traversal
4. 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 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:

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.

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