# Invert Binary Tree | Recursive and Iterative solution

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

For example,

#### 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++

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++

2. Using Stack –

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

## C++

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.

(1 votes, average: 5.00 out of 5)

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂