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].
Overview: 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.
Read the full Palo Alto Networks Software Engineer interview experience this question came from
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.