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).