Invert given Binary Tree | Recursive and Iterative solution

Given a binary tree, write an efficient algorithm to invert binary tree.

 


For example,
 

invert binary tree

 


 

Recursive solution –

This is one of the most famous interview question and can be easily solved recursively. We traverse the tree in preorder fashion and for every node encountered we swap its left and right child before recursively inverting its left subtree and right subtree. We can also traverse the tree in postorder fashion.

C++

Download   Run Complete Code

 
The time complexity of above recursive solution is O(n) and need O(h) extra space for the call stack where h is the height of the tree.
 

Iterative solution –

 

We can easily convert above recursive solution to iterative one by using a queue or stack to store tree nodes.
 

1. Using Queue –
 

The code is almost similar to Level Order Traversal of binary tree.

C++

Download   Run Complete Code

2. Using Stack –
 

The code is almost similar to iterative preorder traversal of binary tree.

C++

Download   Run Complete Code

 
The time complexity of above iterative solutions is O(n) and need O(n) extra space for storing nodes present in any level of binary tree. Worst case happens for a full binary tree, in which last level has n/2 nodes.

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂