Q11: How do you Invert a Binary Tree (flip left and right child pointers)?
Recursively swap the left and right child pointers of every node in the binary tree. Base case: if root == null, return null. Store root.left in a temporary variable, assign root.left = invertTree(root.right), and root.right = invertTree(temp). Return root.
Invert Binary Tree Solution
public class InvertBinaryTree {
public static TreeNode invertTree(TreeNode root) {
if (root == null) return null;
TreeNode temp = root.left;
root.left = invertTree(root.right);
root.right = invertTree(temp);
return root;
}
}💡 Swaps left and right children recursively across the tree.
Key Takeaways
- Recursive post-order / pre-order traversal pointer swapping.
- Time Complexity: $O(n)$, visiting every tree node once.
Knowledge Check
What is the maximum recursion stack depth when inverting a completely skewed degenerate tree with N nodes?