Mirror a binary tree and analyze complexity
Company: Palo Alto Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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].
Quick Answer: This question evaluates understanding of binary tree manipulation and traversal methods, emphasizing recursion and iterative approaches as well as the ability to reason about time and space complexity.
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
Input: ([5, 3, 8, None, 4, 7, 9],)
Expected 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.
Input: ([],)
Expected Output: []
Explanation: An empty tree remains empty.
Hints
- At each node, the work is local: swap its left and right children, then continue on the two subtrees.
- If the tree can be very deep or highly unbalanced, an iterative traversal with a queue can avoid recursion-depth issues.