Mirror a binary tree and analyze complexity
Company: Palo Alto Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
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.
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.
Input: ([1],)
Expected Output: [1]
Explanation: A single-node tree is unchanged after mirroring.
Input: ([1, 2, None, 3, None, 4],)
Expected Output: [1, None, 2, None, 3, None, 4]
Explanation: A left-skewed tree becomes a right-skewed tree.
Input: ([2, 2, 2, None, 3, None, 3],)
Expected Output: [2, 2, 2, 3, None, 3]
Explanation: Duplicate values do not change the logic; all left and right pointers are still swapped.
Solution
def solution(values):
from collections import deque
class TreeNode:
__slots__ = ('val', 'left', 'right')
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(levels):
if not levels or levels[0] is None:
return None
root = TreeNode(levels[0])
queue = deque([root])
i = 1
while queue and i < len(levels):
node = queue.popleft()
if i < len(levels):
left_val = levels[i]
i += 1
if left_val is not None:
node.left = TreeNode(left_val)
queue.append(node.left)
if i < len(levels):
right_val = levels[i]
i += 1
if right_val is not None:
node.right = TreeNode(right_val)
queue.append(node.right)
return root
def mirror_recursive(node):
if node is None:
return None
node.left, node.right = mirror_recursive(node.right), mirror_recursive(node.left)
return node
def mirror_iterative(root):
if root is None:
return None
queue = deque([root])
while queue:
node = queue.popleft()
node.left, node.right = node.right, node.left
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
return root
def serialize(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
if node is None:
result.append(None)
else:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
while result and result[-1] is None:
result.pop()
return result
root = build_tree(values)
# Both recursive and iterative mirroring methods are implemented above.
# The iterative version is used by default to avoid recursion-depth issues
# on highly unbalanced trees.
mirrored_root = mirror_iterative(root)
return serialize(mirrored_root)
Time complexity: O(n) for both recursive and iterative mirroring, where n is the number of nodes.. Space complexity: O(n) overall in this reference solution due to tree construction and serialization; the mirror step itself uses O(h) recursion stack for the recursive version or O(w) queue space for the iterative version, where h is the height and w is the maximum width of the tree..
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.