Mirror Trees
Filed under Goldman Sachs
Free read 1 of 3Confirm definition of mirror trees: root values must be equal, and left subtree of T1 must mirror right subtree of T2.
The question
Given the roots of two binary trees, determine whether they are mirror images of each other (symmetric structure and values with left and right swapped).
Constraints
- Tree nodes contain integer values.
- Number of nodes can range from 0 to 10^4.
Examples
- Input
- root1 = [1,2,2,3,4,4,3], root2 = [1,2,2,3,4,4,3] (structured symmetrically)
- Output
- True
- Why
- The left subtree of root1 mirrors the right subtree of root2 and vice versa.
Approach
Confirm definition of mirror trees: root values must be equal, and left subtree of T1 must mirror right subtree of T2.
Serialize one tree into a specific traversal order and compare, but recursion is cleaner and standard.
Recursive DFS: compare root1.val and root2.val, then recursively check root1.left with root2.right and root1.right with root2.left.
Both roots are None (True), one root is None (False).
Solution
O(N) time, O(H) space
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def is_mirror(root1, root2):
if not root1 and not root2:
return True
if not root1 or not root2:
return False
return (root1.val == root2.val and
is_mirror(root1.left, root2.right) and
is_mirror(root1.right, root2.left))
Tips
- What they are testing: Test with empty trees, single-node trees, asymmetric trees, and structurally identical but non-mirrored trees.
- Common mistake: Checking if two trees are identical instead of checking if one is a mirror of the other (left vs right).
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.