Given the root of a binary tree, invert the tree and return its root. Inverting a binary tree means swapping every node’s left and right children, producing a mirror image of the original tree. The tree may contain between 0 and 100 nodes with values in the range [-100, 100].
Example
Input: 4 Output: 4
/ \ / \
2 7 7 2
/ \ / \ / \ / \
1 3 6 9 9 6 3 1
Every node’s left and right children are swapped, producing a mirror image of the original tree.
Recursively swap the left and right children at every node. Start at the root, swap its two children, then invert the left subtree and the right subtree. The base case is a null node, which you simply return as-is.
Why this works
Every node in a mirrored tree has its left and right children swapped compared to the original. By swapping children at each node and recursing downward, every level of the tree gets mirrored. The recursion naturally handles all depths because each subtree is itself a smaller tree to invert.
Step by step
- Base case — if the node is null, there is nothing to invert, so return null.
- Swap the children — exchange the left and right child pointers of the current node.
- Recurse left and right — apply the same inversion to both subtrees so every level gets mirrored.
- Return the root — the tree is now fully inverted under this node.
Time: O(n)
Space: O(h)
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { this.val = val; }
}
class Solution {
public TreeNode invertTree(TreeNode root) {
if (root == null) {
return null;
}
TreeNode temp = root.left; // swap left and right children
root.left = root.right;
root.right = temp;
invertTree(root.left); // recurse into what was originally the right subtree
invertTree(root.right);
return root;
}
}
struct TreeNode {
int val;
TreeNode *left, *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (!root) {
return nullptr;
}
swap(root->left, root->right); // swap children before recursing
invertTree(root->left); // recurse into what was originally the right subtree
invertTree(root->right);
return root;
}
};
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invertTree(root: TreeNode | None) -> TreeNode | None:
if not root:
return None
root.left, root.right = root.right, root.left # swap children before recursing
invertTree(root.left) # recurse into what was originally the right subtree
invertTree(root.right)
return root