Mirror a binary tree and analyze complexity

Given the root of a binary tree, convert it to its mirror by swapping every node’s left and right children. Implement both recursive and iterative (using a stack or queue) solutions, analyze time and space complexity, and discuss edge cases (empty tree, single node, highly unbalanced). Perform a dry run on this tree (level order): [5,3,8,null,4,7,9].

Mirror a Binary Tree

Given a binary tree in level-order list form, convert it into its mirror by swapping every node's left and right children.

Your task is to return the mirrored tree in the same compact level-order format, using None for missing children when needed and removing trailing None values.

In an interview, you should also be able to explain both approaches:

1. A recursive DFS solution
2. An iterative solution using a stack or queue

Edge cases to think about include an empty tree, a single-node tree, and a highly unbalanced tree.

Dry run for [5, 3, 8, None, 4, 7, 9]:

• Swap children of 5 -> left becomes 8, right becomes 3
• Swap children of 8 -> left becomes 9, right becomes 7
• Swap children of 3 -> left becomes 4, right becomes None Final mirrored tree in level order: [5, 8, 3, 9, 7, 4]

Constraints

• 0 <= len(values) <= 100000
• Each non-null node value is an integer in the range [-10^9, 10^9]
• The input list represents a valid binary tree in compact level-order form

Examples

Example 1

Input: ([5, 3, 8, None, 4, 7, 9],)
Output: [5, 8, 3, 9, 7, 4]

Explanation: After mirroring, 8 moves to the left of 5, 3 moves to the right, and their children are swapped as well.

Example 2

Input: ([],)
Output: []

Explanation: An empty tree remains empty.

Hints

1. At each node, the work is local: swap its left and right children, then continue on the two subtrees.
2. If the tree can be very deep or highly unbalanced, an iterative traversal with a queue can avoid recursion-depth issues.