EasyBlind75TreeDFSBFS
Invert Binary Tree
Given the root of a binary tree, invert the tree, and return its root. Inverting means swapping the left and right children of every node.
Examples
Input
root = [4,2,7,1,3,6,9]
Output
[4,7,2,9,6,3,1]
Swap left and right children of every node.
Input
root = [2,1,3]
Output
[2,3,1]
Swap left and right children.
Constraints
- •
The number of nodes in the tree is in the range [0, 100] - •
-100 <= Node.val <= 100
Approaches
Use BFS to visit each node and swap its children.
CodeT: O(n) | S: O(n)
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invert_tree(root):
if not root:
return None
queue = deque([root])
while queue:
node = queue.popleft()
node.left, node.right = node.right, node.left
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return rootRecursively invert left and right subtrees, then swap them.
CodeT: O(n) | S: O(h)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invert_tree(root):
if not root:
return None
root.left, root.right = root.right, root.left
invert_tree(root.left)
invert_tree(root.right)
return rootInvert children after inverting subtrees.
Diagram
Original: 4->2,7->1,3 and 6,9
Inverted: 4->7,2->9,6 and 3,1
CodeT: O(n) | S: O(h)
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def invert_tree(root):
if not root:
return None
invert_tree(root.left)
invert_tree(root.right)
root.left, root.right = root.right, root.left
return rootComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| BFS - Level Order | O(n) | O(n) | Use BFS to visit each node and swap its children. |
| DFS - Recursive | O(n) | O(h) | Recursively invert left and right subtrees, then swap them. |
| DFS - Post-order | O(n) | O(h) | Invert children after inverting subtrees. |
BFS - Level Order
T: O(n)S: O(n)
Use BFS to visit each node and swap its children.
DFS - Recursive
T: O(n)S: O(h)
Recursively invert left and right subtrees, then swap them.
DFS - Post-order
T: O(n)S: O(h)
Invert children after inverting subtrees.
Common Mistakes
Forgetting to return the root after inversion
Not handling the base case of a null node
Swapping values instead of pointers (works but less clean)