JavaScript | Invert Tree | Mirror Tree | Data Structure

An inverted form of a Binary Tree is another Binary Tree with left and right children of all non-leaf nodes interchanged. You may also call it the mirror of the input tree.

You can observe that the root’s left pointer started pointing towards the right child and the right pointer towards the left child and a similar condition is noticed for all the sub root nodes.

Recursive Solution

The key insight here is to realize that in order to invert a binary tree we only need to swap the children and recursively solve the two smaller sub-problems (same problem but for smaller input size) of left and right sub-tree.

• When the tree is empty return NULL. This is also our base case to stop recursive calls.
• For every node encountered we swap its left and right child before recursively inverting its left and right subtree.

var invertTree = function(root) {
    if(!root) return root;
    
   function traverse(node) {
        if(!node) return null;
        const newNode = { val: node.val };
        newNode.left = traverse(node.left);
        newNode.right = traverse(node.right);
        
        //swap
        let temp = newNode.left;
        newNode.left = newNode.right;
        newNode.right = temp;
        return newNode;
    }
    
    return traverse(root);
};

Complexity Analysis

In the above approach, we are traversing each node of the tree only once. Time complexity: O(n)

Let’s connect on LinkedIn! Please read more for more data structure javascript question and don’t forget to follow me for more such articles.