Invert Binary Tree

79.5k
0

Problem Statement

Given the root of a binary tree, invert the tree by swapping the left and right children of every node.

Return the root of the inverted binary tree.

Example 1

Input:
root = [4, 2, 7, 1, 3, 6, 9]

Output:
[4, 7, 2, 9, 6, 3, 1]

Explanation:
The left and right children of every node are swapped, producing the mirror image of the original binary tree.

Example 2

Input:
root = [2, 1, 3]

Output:
[2, 3, 1]

Explanation:
The left child 1 and right child 3 of the root are exchanged.

Approach 1

Inverting the entire tree requires the same operation to be performed at every node: its left and right subtrees are exchanged.

This naturally fits recursion. Once a node is reached, its children are swapped, and the same operation is recursively applied to both resulting subtrees.

Each recursive call is responsible only for the subtree rooted at its current node. Once all calls have finished, the left and right relationships of every node have been reversed.

Algorithm

  • If the current node is null, the recursive call is terminated because no subtree is available to invert.

  • The left and right children of the current node are swapped so that its immediate subtree is inverted.

  • The new left subtree is recursively inverted because the same transformation is required for every node inside it.

  • The new right subtree is recursively inverted in the same way.

  • After both subtrees have been processed, the current node is returned as the root of the inverted subtree.

  • When this process is started from the root, the completely inverted binary tree is obtained.

Dry Run

Invert Binary Tree Appraoch 1 Dry Run.png

Invert Binary Tree Appraoch 1 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
public:
// Recursively swaps the children
// of every node in the subtree.
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
// Swapping the children mirrors
// the current node's subtree.
swap(root->left, root->right);
invertTree(root->left);
invertTree(root->right);
return root;
}
};
int main() {
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(7);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(9);
Solution solution;
root = solution.invertTree(root);
return 0;
}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is visited exactly once.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. This becomes O(N) for a skewed tree and O(log N) for a balanced tree.

Approach 2

Recursion is not required to invert the tree. It is sufficient for every node to be visited once and for its children to be swapped.

BFS processes the tree level by level using a queue. Whenever a node is removed from the queue, its left and right children are exchanged. The resulting children are then inserted into the queue so that their subtrees can be processed later.

Once the queue becomes empty, every node has been visited and inverted.

Algorithm

  • If the root is null, it is returned immediately because an empty tree is already inverted.

  • The root is inserted into a queue so that the tree can be processed level by level.

  • While the queue is not empty, one node is removed and its left and right children are swapped.

  • If the swapped left child exists, it is inserted into the queue so that its subtree can be processed later.

  • If the swapped right child exists, it is inserted into the queue for the same reason.

  • After every node has been processed and the queue becomes empty, the root is returned as the root of the inverted tree.

Dry Run

Invert Binary Tree Appraoch 2 Dry Run.png

Invert Binary Tree Appraoch 2 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
public:
// Inverts the tree level by level
// using breadth-first traversal.
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
queue<TreeNode*> nodesQueue;
nodesQueue.push(root);
// Every node is processed once
// and its children are exchanged.
while (!nodesQueue.empty()) {
TreeNode* node =
nodesQueue.front();
nodesQueue.pop();
swap(node->left, node->right);
// Swapped children are queued so
// their subtrees are processed later.
if (node->left != nullptr) {
nodesQueue.push(node->left);
}
if (node->right != nullptr) {
nodesQueue.push(node->right);
}
}
return root;
}
};
int main() {
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(7);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(9);
Solution solution;
root = solution.invertTree(root);
return 0;
}

Complexity Analysis

Let N be the number of nodes in the binary tree and W be the maximum width of the tree, meaning the maximum number of nodes present at any single level.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is inserted into and removed from the queue exactly once.

Space Complexity: O(W), where W is the maximum width of the binary tree, because the queue may contain all nodes of a level at the same time. In the worst case, W can become O(N).

Approach 3

The same transformation can also be performed iteratively using depth-first traversal.

Instead of a queue, a stack is used. Each node is removed from the stack, its left and right children are swapped, and its existing children are then inserted into the stack for later processing.

The exact order in which the nodes are visited does not affect the final result. What matters is that the children of every node are exchanged exactly once.

This provides an iterative DFS solution while avoiding recursion.

Algorithm

  • If the root is null, it is returned immediately because no inversion is required.

  • The root is inserted into a stack so that iterative DFS can begin.

  • While the stack is not empty, the current node is removed and its left and right children are swapped.

  • Each non-null child is inserted into the stack so that its subtree is eventually processed.

  • The process is continued until the stack becomes empty, ensuring that every node has been visited and inverted.

  • The root is then returned as the root of the inverted binary tree.

Dry Run

Invert Binary Tree Appraoch 3 Dry Run.png

Invert Binary Tree Appraoch 3 Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
public:
// Inverts the tree using an explicit
// stack for depth-first traversal.
TreeNode* invertTree(TreeNode* root) {
if (root == nullptr) {
return nullptr;
}
stack<TreeNode*> nodesStack;
nodesStack.push(root);
// Every popped node is inverted
// before its children are processed.
while (!nodesStack.empty()) {
TreeNode* node =
nodesStack.top();
nodesStack.pop();
swap(node->left, node->right);
// Existing children are stored so
// their subtrees are inverted later.
if (node->right != nullptr) {
nodesStack.push(node->right);
}
if (node->left != nullptr) {
nodesStack.push(node->left);
}
}
return root;
}
};
int main() {
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(7);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
root->right->left = new TreeNode(6);
root->right->right = new TreeNode(9);
Solution solution;
root = solution.invertTree(root);
return 0;
}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N), where N is the number of nodes in the binary tree. Every node is pushed onto and removed from the stack exactly once.

Space Complexity: O(H), where H is the height of the binary tree, for the explicit DFS stack. In the worst case, this is bounded by O(N).

Interview follow-up Questions

No. A node's children may be swapped before its subtrees are recursively processed, or the original subtrees may first be inverted and then swapped. Both methods produce the same result as long as every node's children are exchanged exactly once.

Binary Tree

Read Similar Blogs

Binary Tree

Parent and Distance - Introduction

Parent and Distance in a Binary Tree A binary tree normally stores connections from a node to its children: Left child Right child These connections make downward traversal straightforward. However...

117.9k
Binary Tree

Check If a Binary Tree Is a Subtree of Another Tree

tuf-code-editor-1 cpp #include using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int value) { val = value; left = nullptr; right = nullptr; } }; class Soluti...

67.9k
Binary Tree

Count Nodes in a Complete Binary Tree

Given the root of a complete binary tree , determine the total number of nodes present in the tree. In a complete binary tree: Every level except possibly the last is completely filled. Nodes in th...

54.2k
Comments0