Invert Tree¶
Problem¶
Given the root of a binary tree, invert the tree so that every left child becomes the right child and vice versa.
Approach¶
Recursive swap: at each node, swap left and right children, then recurse into both subtrees.
When to Use¶
Tree transformation — "mirror", "invert", "flip". Any problem requiring symmetric restructuring of a tree in-place. Pattern: swap children, then recurse into both subtrees.
Complexity¶
| Time | O(n) |
| Space | O(h) where h = height of tree (call stack) |
Implementation¶
invert_tree ¶
Invert (mirror) a binary tree.
Problem
Given the root of a binary tree, invert the tree so that every left child becomes the right child and vice versa.
Approach
Recursive swap: at each node, swap left and right children, then recurse into both subtrees.
When to use
Tree transformation — "mirror", "invert", "flip". Any problem requiring symmetric restructuring of a tree in-place. Pattern: swap children, then recurse into both subtrees.
Complexity
Time: O(n) Space: O(h) where h = height of tree (call stack)
invert_tree ¶
Invert a binary tree in place and return the root.
t = TreeNode(1, TreeNode(2), TreeNode(3)) r = invert_tree(t) r.left.val, r.right.val # type: ignore[union-attr] (3, 2)
Source code in src/algo/trees/invert_tree.py
"""Tests for invert binary tree."""
from algo.trees.invert_tree import TreeNode, invert_tree
def _to_list(root: TreeNode | None) -> list[int | None]:
"""BFS serialization for easy comparison."""
if not root:
return []
from collections import deque
result: list[int | None] = []
queue: deque[TreeNode | None] = deque([root])
while queue:
node = queue.popleft()
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
# Strip trailing Nones for cleaner output.
while result and result[-1] is None:
result.pop()
return result
class TestInvertTree:
def test_basic(self) -> None:
tree = TreeNode(
4,
TreeNode(2, TreeNode(1), TreeNode(3)),
TreeNode(7, TreeNode(6), TreeNode(9)),
)
result = invert_tree(tree)
assert _to_list(result) == [4, 7, 2, 9, 6, 3, 1]
def test_empty_tree(self) -> None:
assert invert_tree(None) is None
def test_single_node(self) -> None:
tree = TreeNode(1)
result = invert_tree(tree)
assert _to_list(result) == [1]
def test_left_only(self) -> None:
tree = TreeNode(1, TreeNode(2))
result = invert_tree(tree)
assert result is not None
assert result.left is None
assert result.right is not None
assert result.right.val == 2
def test_double_invert_restores(self) -> None:
tree = TreeNode(1, TreeNode(2, TreeNode(4), None), TreeNode(3))
original = _to_list(tree)
invert_tree(tree)
invert_tree(tree)
assert _to_list(tree) == original
def test_returns_same_root(self) -> None:
tree = TreeNode(5, TreeNode(3), TreeNode(8))
result = invert_tree(tree)
assert result is tree
Implement it yourself
Run: just challenge trees invert_tree
Then implement the functions to make all tests pass.
Use just study trees for watch mode.
Reveal Solution
invert_tree ¶
Invert (mirror) a binary tree.
Problem
Given the root of a binary tree, invert the tree so that every left child becomes the right child and vice versa.
Approach
Recursive swap: at each node, swap left and right children, then recurse into both subtrees.
When to use
Tree transformation — "mirror", "invert", "flip". Any problem requiring symmetric restructuring of a tree in-place. Pattern: swap children, then recurse into both subtrees.
Complexity
Time: O(n) Space: O(h) where h = height of tree (call stack)
invert_tree ¶
Invert a binary tree in place and return the root.
t = TreeNode(1, TreeNode(2), TreeNode(3)) r = invert_tree(t) r.left.val, r.right.val # type: ignore[union-attr] (3, 2)