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.

--

--

--

Working in Walmart as UI Developer | Mentor | React | JavaScript | HTML | CSS

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Add Facial Recognition to Your App Easily With face-api.js

Emotion detection using face-api

NEM Blockchain Faucet and Transactions using ReasonML; Let’s get this bread pt.2🥖😎

Proper way to use error handling in Javascript

Understanding React props

TIL/2020–11–29

How to Add Authentication to Your Fastify REST API Using Auth0

How to use Moment.js with Vue 3?

Use SPFx with Angular and Angular CLI

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
iAmSonika | www.startlearncoding.com

iAmSonika | www.startlearncoding.com

Working in Walmart as UI Developer | Mentor | React | JavaScript | HTML | CSS

More from Medium

JavaScript: Deep Dive into Functions - Part 4

Explaining First Class Functions in Javascript

JavaScript Algorithms: Maximum Subarray(LeetCode)

ES6 Key Features Every JavaScript Developer Must Know