Inverting a binary tree

Lately I’ve been solving a lot of LeetCode problems, most of them revolving around recursion.

With that, I finally came to understand binary trees, and while I used to struggle a lot at the beginning, right now most of the problems seem a bit trivial.

The code

Without any further ado, first here’s my response:

  var invertTree = function (root) {
    function invert(node) {
        if (node === null) {
            return;
        }
        let temp = node.left;
        node.left = node.right;
        node.right = temp;
        invert(node.left);
        invert(node.right);
    }
    invert(root);
    return root;
};

Elegant and easy, right? Now let’s explain what’s happening:

We know that every tree can have

• a left child,
• a right child,
• or both.

To invert a binary tree, we want to swap every node’s left and right children throughout the entire tree.

Here’s how the code works step by step:

1. Base Case: If the current node is “null”, we simply return “null”. This stops the recursion when we reach the leaves.

2. Swap Children: For the current node, we swap its left and right children.

3. Recursive Calls: We recursively invert the left and right subtrees (which have just been swapped).

This process continues until every node in the tree has had its children swapped, resulting in a fully inverted (mirrored) binary tree.

This approach uses recursion, which is a natural fit for tree problems because each subtree is itself a tree.

  var invertTree = function (root) {
    function invert(node) { 
        if (node === null) { //First we always check if the node is null
            return; // Here's the end game, if the node is null then we have nothing else to do, we return.
        }
        let temp = node.left; // We need to create a temporal copy of one of the nodes.
        node.left = node.right; //Swap left for right
        node.right = temp; // Swap right for temporal
        invert(node.left); // Let's repeat the process with left...
        invert(node.right); // And Right
    }
    invert(root);
    return root;
};

Conclusion

This method is both concise and efficient, making it a perfect solution for this classic problem.