Skip to main content

10. Same Tree

easyAsked at ServiceNow

Given two binary trees, decide whether they are structurally identical and have equal values. ServiceNow asks this to verify recursive tree equality fluency — the same shape they apply when diffing two snapshots of a workflow definition.

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

Source citations

Public interview reports confirming this problem appears in ServiceNow loops.

  • Glassdoor (2026-Q2)— ServiceNow recursion warmups frequently include this.
  • LeetCode Discuss (2025-10)— ServiceNow loops cite it as a 15-minute screener.

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

Serialize both trees via preorder (with null markers) and string-compare.

Time
O(n)
Space
O(n)
function isSameTree(p, q) {
  const ser = (n) => !n ? '#' : `${n.val},${ser(n.left)},${ser(n.right)}`;
  return ser(p) === ser(q);
}

Tradeoff: Correct but allocates two huge strings. Mention only as the lazy answer.

2. Recursive structural compare

If both null return true. If one null return false. Otherwise compare values and recurse on left and right subtrees.

Time
O(n)
Space
O(h) recursion stack
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 time, recursion-stack space. Short-circuits on first mismatch — a property ServiceNow grades for in workflow-diff code.

ServiceNow-specific tips

ServiceNow grades for the three-case structure — both null (equal), one null (unequal), values differ (unequal). Bonus signal: mention that && short-circuits, so a left-subtree mismatch never explores the right — same shape their workflow-diff tool uses to bail early on the first difference.

Common mistakes

  • Forgetting one of the three base cases — e.g., returning true when both are null but not handling the 'one null, one not' case.
  • Comparing references (p === q) instead of values — fails when trees are deep clones.
  • Recursing left and right separately and OR-ing — must be AND.

Follow-up questions

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

  • Symmetric Tree (LC 101).
  • Subtree of Another Tree (LC 572).
  • How would you implement iteratively with two stacks/queues?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

What about iterative?

Use two queues; push both roots; on each step pop one pair, compare, then push their corresponding children. Same time, slightly different space profile.

Does order of recursion matter?

Logically no — left/right is symmetric. In practice the JIT may benefit from consistent order, but interviewers don't grade that.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →