AlgoDaily - Invert a Binary Tree - Complexity Of Final Solution

So, to put it all together: we can perform an in-order traversal and do a swap at each iteration.

A caveat that was pointed out by readers — if we’re dealing with a substantially large binary tree, then a recursive solution might cause problems due to call stack size. There are two ways to get around this:

Using a stack to mimic the recursion
Using a queue, visiting the levels one by one in a BFS fashion and swapping the left and right nodes to invert the tree.

Here’s what the final code looks like:

JAVASCRIPT

1function invertTree(head) {
2  if (head) {
3    var temp = head.left;
4    head.left = head.right;
5    head.right = temp;
6
7    invertTree(head.left);
8    invertTree(head.right);
9  }
10
11  return head;
12}

Complexity of Final Solution

Let n be the number of nodes in the binary tree. We traverse through all n nodes using recursion for O(n) time complexity, and we can have up to logn recursive calls on the stack at once where logn is the depth of the tree for O(logn) space complexity.

xxxxxxxxxx
  assertIsFunction(invertTree, '`invertTree` should be a function');
 
var assert = require('assert');
​
function invertTree(head) {
  return;
}
​
function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}
​
// Regular binary trees
var tree1 = new Node(4);
tree1.left = new Node(1);
tree1.right = new Node(3);
​
var tree2 = new Node(5);
tree2.left = new Node(10);
tree2.left.left = new Node(17);
tree2.left.right = new Node(3);
tree2.right = new Node(8);
​
// Binary search trees
var tree3 = new Node(6);
tree3.left = new Node(3);
​

OUTPUT

Results will appear here.