Invert a binary tree | Recursive and Iterative solutions

Given a binary tree, invert it. When a binary tree is inverted it returns its mirror.

Example

Input:
     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:
     4
   /   \
  7     2
 / \   / \
9   6 3   1

It is one of the most common questions asked in interviews and in this example we will see how to implement it recursively as well as iteratively.

Invert the binary tree recursively.

By observing the above image we can notice that inversion or mirror of binary is tree is nothing but swapping of its left and child nodes at each level.

Acknowledging that we can derive a recursive solution.

• Traverse the tree in pre-order or post-order way.
• And in each iteration swap its left and child and then invert its left and right subtree by calling them recursively.

Pseudo code

//post order
Invert(left-subtree)
Invert(right-subtree)
Swap left and right subtrees.

//pre order
Swap left and right subtrees
Invert(left-subtree)
Invert(right-subtree)

Using pre-order traversal

//swap nodes
const swap = (node) => {
  const { left, right} = node;
  node.left = right;
  node.right = left;
}

const invertBinaryTree = (root) => {
  //Base case
  if(root === null){
    return;
  } 
  
  //Swap the left subtree with right subtree
  swap(root);
  
  //Invert left subtree
  invertBinaryTree(root.left);
  
  //Invert right subtree
  invertBinaryTree(root.right)
}

Input:
const preorder = (tree) => {
  if(tree === null){
    return;
  }
  
  console.log(tree.val);
  preorder(tree.left);
  preorder(tree.right);
}

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

const tree = new Node(4);  
tree.left = new Node(2);  
tree.right = new Node(7);  
tree.left.left = new Node(1);  
tree.left.right = new Node(3);  
tree.right.left = new Node(6);  
tree.right.right = new Node(9);  

invertBinaryTree(tree);
preorder(tree);

Output:
4 7 9 6 2 3 1


     4
   /   \
  7     2
 / \   / \
9   6 3   1

Time complexity: O(n).
Space complexity: O(h) where h is the height of the tree.

---

Iterative solution.

The above recursive solution can be converted to iterative one by using queue or stack to store the nodes of the tree.

Using queue

To invert the tree iteratively,

• Perform the level order traversal using the queue.
• Store the root node in the queue and then keep on iterating the loop till the queue is not empty.
• In each iteration get the top node, swap its left and right child and then add the left and right subtree back to the queue.

const invertTreeUsingQueue = (root) => {
  //Base case
  if(root === null){
    return;
  }
  
  //Create a queue and add the root at the top
  const q = [];
  q.unshift(root);
  
  //iterate till queue has any node
  while(q.length){
    //get top node
    const curr = q.pop();
    
    //Swap left child with right child of the node
    swap(curr);
     
    //Push left child to the queue
    if(curr.left !== null){
      q.unshift(curr.left);
    }
    
    //Push right child to the queue
    if(curr.right !== null){
      q.unshift(curr.right);
    }
  }
}

Input:
const preorder = (tree) => {
  if(tree === null){
    return;
  }
  
  console.log(tree.val);
  preorder(tree.left);
  preorder(tree.right);
}

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

const tree = new Node(4);  
tree.left = new Node(2);  
tree.right = new Node(7);  
tree.left.left = new Node(1);  
tree.left.right = new Node(3);  
tree.right.left = new Node(6);  
tree.right.right = new Node(9);  

invertBinaryTree(tree);
preorder(tree);

Output:
4 7 9 6 2 3 1

     4
   /   \
  7     2
 / \   / \
9   6 3   1

---

Using stack

We can perform the above operation using stack as well. It is like traversing the tree preorder fashion.

const invertTreeUsingStack = (root) => {
  //Base case
  if(root === null){
    return;
  }
  
  //Create a stack and add the root node at the top
  const s = [];
  s.unshift(root);
  
  //iterate till stack has any node
  while(s.length){
    //get top node from stack
    const curr = s.shift();
    
    //Swap left child with right child of the node
    swap(curr);
     
    //Push left child to the stack
    if(curr.left !== null){
      s.unshift(curr.left);
    }
    
    //Push right child to the stack
    if(curr.right !== null){
      s.unshift(curr.right);
    }
  }
}

Input:
const preorder = (tree) => {
  if(tree === null){
    return;
  }
  
  console.log(tree.val);
  preorder(tree.left);
  preorder(tree.right);
}

function Node(val) {
  this.val = val;
  this.left = null;
  this.right = null;
}

const tree = new Node(4);  
tree.left = new Node(2);  
tree.right = new Node(7);  
tree.left.left = new Node(1);  
tree.left.right = new Node(3);  
tree.right.left = new Node(6);  
tree.right.right = new Node(9);  

invertBinaryTree(tree);
preorder(tree);

Output:
4 7 9 6 2 3 1

     4
   /   \
  7     2
 / \   / \
9   6 3   1

For both iterative solutions
Time complexity: O(n).
Space complexity: O(n).