Invert Binary Tree

Mirror a binary tree: swap the left and right children of every node, and return the root. Trees are written in level order with null for missing children: [4, 2, 7, 1, 3, 6, 9].

Examples

Input:  root = [4, 2, 7, 1, 3, 6, 9]
Output: [4, 7, 2, 9, 6, 3, 1]

Input:  root = [2, 1, 3]
Output: [2, 3, 1]

Constraints

• 0 ≤ nodes ≤ 100

Explanation

Recursive

A tree is mirrored when its root’s children are swapped and both subtrees are mirrored. That definition is the code: swap left and right, then invert each child. The base case is an empty tree.

Iterative

BFS (or DFS with a stack): pop a node, swap its children, push the children. Same result without recursion.

Complexity

• Time: O(n) — each node visited once. Space: O(h) for recursion, where h is the tree height (O(n) worst case for a skewed tree).