Invert Binary Tree
Problem Description
Given the root of a binary tree, invert the tree, and return its root.
Example 1:
Example 2:
Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Solve it on LeetCode
Approaches
1. Recursive Approach
Intuition:
The recursive approach is elegant and leverages the natural recursive structure of trees. The idea is to swap the left and right children of a node recursively. For each node, invert the left subtree and the right subtree. This results in a mirrored version of the original tree.
Code:
- Time Complexity: O(n) - We visit each node exactly once.
- Space Complexity: O(h) - The recursion stack space is proportional to the height of the tree
h.
2. Iterative Approach Using BFS
Intuition:
We can also solve this problem iteratively using a breadth-first search (BFS) approach. The idea is to use a queue to perform a level-order traversal of the tree. At each node, swap the left and right children.
Code:
- Time Complexity: O(n) - Each node is visited once.
- Space Complexity: O(n) - In the worst case, the queue will hold all the nodes in a level of the tree.
3. Iterative Approach Using DFS with Stack
Intuition:
Another iterative method is using depth-first search (DFS) with a stack. Similar to BFS, traverse the tree and swap left and right children for each node encountered.
Code:
- Time Complexity: O(n) - Every node is pushed and popped from the stack once.
- Space Complexity: O(n) - In the worst case, the stack will hold all nodes in a path from root to a leaf.