Invert Binary Tree
The problem
Swap the left and right children at every node of a binary tree and return its root. An empty tree stays empty.
Example
Root 4 with children 2 and 7 becomes root 4 with children 7 and 2.
Need a hint?
The same operation applies independently to every subtree.
Write pseudocode, trace the example, or note an edge case. This scratchpad does not run code.
Notes stay in this browser when storage is available.
Read the solution approach
For a non-null node, swap its children and recursively invert both. The base case returns immediately for null. A queue or stack can perform the same traversal iteratively when recursion depth is a concern.
Complexity
O(n) time and O(h) recursive stack space for height h.
Before moving on, explain why the algorithm is correct and trace a boundary case without looking at the approach.