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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Recursive function to invert binary Tree using preorder traversal void invertBinaryTree(Node *root) { // base case: if tree is empty if (root == nullptr) return; // swap left subtree with right subtree swap(root->left, root->right); // invert left subtree invertBinaryTree(root->left); // invert right subtree invertBinaryTree(root->right); } |

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Iterative Function to invert binary Tree using queue void invertBinaryTree(Node* root) { // base case: if tree is empty if (root == nullptr) return; // maintain a queue and push push root node queue<Node*> q; q.push(root); // run till queue is not empty while (!q.empty()) { // pop top node from queue Node* curr = q.front(); q.pop(); // swap left child with right child swap(curr->left, curr->right); // push left child of popped node to the queue if (curr->left) q.push(curr->left); // push right child of popped node to the queue if (curr->right) q.push(curr->right); } } |

**2. Using Stack – **

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

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
// Data structure to store a Binary Tree node struct Node { int data; Node *left, *right; }; // Iterative Function to invert binary Tree using stack void invertBinaryTree(Node* root) { // base case: if tree is empty if (root == nullptr) return; // create an empty stack and push root node stack<Node*> s; s.push(root); // run till stack is not empty while (!s.empty()) { // pop top node from stack Node* curr = s.top(); s.pop(); // swap left child with right child swap(curr->left, curr->right); // push right child of popped node to the stack if (curr->right) s.push(curr->right); // push left child of popped node to the stack if (curr->left) s.push(curr->left); } } |

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

## Leave a Reply

nicely done!