Skip to main content

10. Same Tree

easyAsked at Snowflake

Determine whether two binary trees are structurally identical and have the same values. Snowflake asks this as a recursion warm-up before deeper tree problems, often paired with a structural-equality follow-up on query plans.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2025-Q4)— Snowflake compiler team uses this to set up plan-equality follow-up.
  • LeetCode Discuss (2025-08)— Reported at Snowflake new-grad screens.

Problem

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Constraints

  • The number of nodes in both trees is in the range [0, 100].
  • -10^4 <= Node.val <= 10^4

Examples

Example 1

Input
p = [1,2,3], q = [1,2,3]
Output
true

Example 2

Input
p = [1,2], q = [1,null,2]
Output
false

Example 3

Input
p = [1,2,1], q = [1,1,2]
Output
false

Approaches

1. Serialize and compare strings

Build a canonical string representation of each tree, then compare.

Time
O(n)
Space
O(n)
function isSameTree(p, q) {
  function serialize(n) {
    if (!n) return '#';
    return `${n.val},${serialize(n.left)},${serialize(n.right)}`;
  }
  return serialize(p) === serialize(q);
}

Tradeoff: Works but allocates O(n) string. Don't ship for large trees.

2. Recursive structural compare (optimal)

Both null -> true. One null -> false. Values differ -> false. Otherwise recurse on left and right.

Time
O(n)
Space
O(h)
function isSameTree(p, q) {
  if (!p && !q) return true;
  if (!p || !q) return false;
  if (p.val !== q.val) return false;
  return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

Tradeoff: Linear, no allocations. Short-circuits on first mismatch.

Snowflake-specific tips

Snowflake interviewers want the short-circuit pattern (return false as soon as you find a difference). Bonus signal: pivot to comparing query plans — discuss how Snowflake's planner hashes plan subtrees for the plan cache, and what hash collisions you'd need to be careful about.

Common mistakes

  • Returning true at the leaf without checking that both p AND q are null.
  • Comparing only values, missing the structural difference between [1,2] and [1,null,2].
  • Trying to flatten the tree and compare arrays — loses structural info.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • Symmetric Tree (LC 101).
  • Is one tree a subtree of another (LC 572)?
  • How does Snowflake hash plan subtrees for the plan cache?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why not compare arrays of values?

Arrays lose null-children positions. [1,2] and [1,null,2] would both flatten to [1,2] but they're structurally different trees.

How does plan equality work in a query planner?

Snowflake hashes each plan node (operator + child hashes + key arguments) bottom-up. Plans with the same hash are candidates for cache reuse. The shape is exactly this recursive compare.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →