Invert Binary Tree
Problem Statement
Given the root of a binary tree, invert the tree, and return its root. To invert a binary tree, you need to swap the left and right children for each node in the tree.
Constraints:
- The number of nodes in the tree is in the range [0, 100]
- -100 <= Node.val <= 100
Input Format:
- The root of a binary tree
Output Format:
- The root of the inverted binary tree
Examples:
Example 1:
Input:
root = [4,2,7,1,3,6,9]
Output:
[4,7,2,9,6,3,1]
Explanation:
The original tree is: 4 / \ 2 7 / \ / \ 1 3 6 9 The inverted tree is: 4 / \ 7 2 / \ / \ 9 6 3 1
Example 2:
Input:
root = [2,1,3]
Output:
[2,3,1]
Explanation:
The original tree is: 2 / \ 1 3 The inverted tree is: 2 / \ 3 1
Example 3:
Input:
root = []
Output:
[]
Explanation:
An empty tree remains empty when inverted.
Solutions
Recursive DFS Approach
Use a depth-first recursive approach to invert the tree. At each node, recursively invert the left and right subtrees, then swap them.
Iterative BFS Approach
Use a breadth-first search approach with a queue to invert the tree level by level.
Algorithm Walkthrough
Example input: nums = []
Step-by-step execution:
- Call invertTree(root) with root node 4
- Recursive call to invertTree(root.left) for node 2
- Recursive call to invertTree(root.left.left) for node 1
- Node 1 has no children, return node 1
- Recursive call to invertTree(root.left.right) for node 3
- Node 3 has no children, return node 3
- Swap children of node 2: left becomes 3, right becomes 1
- Return node 2 with swapped children
- Recursive call to invertTree(root.right) for node 7
- Recursive call to invertTree(root.right.left) for node 6
- Node 6 has no children, return node 6
- Recursive call to invertTree(root.right.right) for node 9
- Node 9 has no children, return node 9
- Swap children of node 7: left becomes 9, right becomes 6
- Return node 7 with swapped children
- Swap children of root node 4: left becomes 7 (with its swapped children), right becomes 2 (with its swapped children)
- Return the root node 4 with completely inverted tree
Hints
Hint 1
Hint 2
Hint 3
Video Tutorial
Video tutorials can be a great way to understand algorithms visually
Visualization
Visualize the recursive process of swapping left and right children at each node in the tree.
Key visualization elements:
- current node
- left subtree
- right subtree
- swapped children
Similar Questions
Binary Tree Level Order Traversal
MediumGiven the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Maximum Depth of Binary Tree
EasyGiven the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Same Tree
EasyGiven the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
Implementation Notes
This problem gained notoriety when Max Howell (creator of Homebrew) tweeted that Google rejected him for not being able to invert a binary tree, despite millions of people using his software. It's now considered a classic binary tree problem and a good introduction to tree recursion.