Skip to main content

11. Symmetric Tree

easyAsked at Lyft

Determine whether a binary tree is a mirror of itself.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given the root of a binary tree, check whether it is symmetric around its center (left subtree is a mirror of the right subtree). Both recursive and iterative answers are acceptable.

Constraints

  • Number of nodes in range [1, 1000]
  • -100 <= node value <= 100

Examples

Example 1

Input
root = [1,2,2,3,4,4,3]
Output
true

Example 2

Input
root = [1,2,2,null,3,null,3]
Output
false

Approaches

1. Inorder + check palindrome

Inorder-collect with sentinel markers, then check the array is a palindrome.

Time
O(n)
Space
O(n)
const a=[]; (function dfs(n){if(!n){a.push('#');return;} dfs(n.left); a.push(n.val); dfs(n.right);} )(root);
return a.join()===a.slice().reverse().join();

Tradeoff:

2. Mirror DFS

Recurse with two pointers moving in opposite directions through left and right subtrees.

Time
O(n)
Space
O(h)
function isSymmetric(root) {
  function mirror(a, b) {
    if (!a && !b) return true;
    if (!a || !b) return false;
    return a.val === b.val && mirror(a.left, b.right) && mirror(a.right, b.left);
  }
  return mirror(root.left, root.right);
}

Tradeoff:

Lyft-specific tips

Lyft engineers prefer the explicit two-pointer mirror recursion; they say it generalises better to two-tree comparisons used in their map-tile cache validation.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Symmetric Tree and other Lyft interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →