Solution Developed In:

The Question

For this article we will be covering Leetcode '226. Invert Binary Tree' question. This question is rated as a Easy question.

Question:

Given the root of a binary tree, invert the tree, and return its root.

Example:

Input: root = [4,2,7,1,3,6,9]
Output: [4,7,2,9,6,3,1]

Explaining The Question

We need to invert a binary tree. As if you held a mirror to the tree.
What this mean's is that at every node, we have to swap the left and right nodes. We continue this until we have no more nodes left.

So by starting from the bottom of the tree, we will swap the left node with the right node and vice versa.

Recommended Knowledge

1. Binary Trees
2. Post Order Travel
3. Array Destructuring. (ES6) (Optional)

What do we know?

1. We have a tree and we gotta invert it. That is to say, left nodes become right nodes and right nodes become left nodes.

How we're going to do it:

We're going to use a Post Order Traversal to invert the tree. Meaning, we will start at the very bottom left of the tree and work our way back up to the root of the tree.

We're then going to swap the left and right nodes. We will do this to every node in the tree until we get back up to the root node

1. As we're going recursively, all we're going to do is swap the left and right nodes on every node we go to.
2. Firstly we do this by checking that a node exists at all. This is for edge cases and for when we reach the end of the tree.
3. We declare a temporary variable to hold the left node (As we're about to override it but still need it for later).
4. We then swap the left and right nodes. With the help of that temporary variable.
5. We then do this for all the left nodes of the given tree, and then all the right nodes of a given tree. The order of this part does not matter, so long as you swap them.
6. Assuming we have swapped our left and right nodes, we return the root node. We do this because we're going to be calling this function recursively. So we can go back up in the stack. But this is mostly important for when we reached the last node in the stack.

Big O Notation:

• Time Complexity: O(n) | Where n is number of tree nodes | Because we go over each node.
• Space Complexity: O(h) | Where h is the maximum height of the tree | Because that will be the size of the call stack | Although it could be argued to be O(n) as the their is a worst case possibility of the call stack being as deep as the ENTIRE tree.

' 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: 61 ms, faster than 87.47% of JavaScript online submissions for Invert Binary Tree.
• Memory Usage: 47 MB, less than 40.24% of JavaScript online submissions for Invert Binary Tree.

Solution 1

    var invertTree = function (root) {
    /* -------------------------------------------------------------------------- */
    /*                           226. Invert Binary Tree                          */
    /* -------------------------------------------------------------------------- */

    // We have reached a leaf node, so we need to bubble back up the stack.
    // To the next node.
    if (!root) {
        return root;
    }

    // A temporary variable to hold the left node (As we're about to override it but still need it for later).
    let temp_node = root.left;

    // We then swap the left and right nodes. With the help of that temporary variable.
    root.left  = root.right;
    root.right = temp_node;

    // We then do this for all the left nodes of the given tree, and then all the right nodes of a given tree.
    invertTree(root.left);
    invertTree(root.right);

    // Assuming we have swapped our left and right nodes, we return the root node.
    return root;
};

Solution 2

 var invertTree = function (root) {

    // We have reached a leaf node, so we need to bubble back up the stack.
    // To the next node.
    if (!root) {
        return root;
    }

    // ES6 Destructuring.
    // What this does is take the left and right nodes and swap them.
    // But without the need of a temp variable. As in object destructuring, it remembers.
    // Although, if you're a performance fanatic, this isn't efficient. 
    [root.left, root.right] = [invertTree(root.right), invertTree(root.left)]

    return root
};