Skip to main content

11. Same Tree

easyAsked at Datadog

Given two binary trees, determine if they are structurally identical with equal node values. Datadog asks this as a baseline tree-recursion question — and follows up by asking how you'd compare two ingestion-state snapshots for drift.

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

Source citations

Public interview reports confirming this problem appears in Datadog loops.

  • Glassdoor (2026-Q1)— Phone screen lead-in question at Datadog.
  • LeetCode Discuss (2025-10)— Listed in Datadog tagged set.

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

Preorder-serialize both trees with null markers; compare strings.

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 strings linear in tree size. Wasteful when an early mismatch could terminate sooner.

2. Recursive short-circuit (optimal)

Both null → equal. One null → unequal. Values differ → unequal. Otherwise recurse on left and right.

Time
O(min(n, m))
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: Short-circuits on first mismatch. Datadog will probe: 'What's the early-exit behavior?' This version stops at the first divergence.

Datadog-specific tips

Datadog interviewers care about early termination — if the two ingestion-state snapshots differ at the root, your code should return false in O(1). Articulate the four base cases (both null, p null, q null, value mismatch) before recursing.

Common mistakes

  • Forgetting the both-null case → null-pointer crash on the value comparison.
  • Comparing p === q (reference equality) instead of values — would return false for structurally identical but distinct trees.
  • Recursing left and right separately and then ANDing — works but loses short-circuit when JS short-circuits anyway in the && expression.

Follow-up questions

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

  • Symmetric Tree (LC 101) — compare a tree with its mirror.
  • Subtree of Another Tree (LC 572) — find one tree inside another.
  • Compare two BSTs in serialized form for replication consistency.

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 check both base cases (both null AND one null)?

If p is null and q isn't (or vice versa), the structures differ. Checking 'both null' alone wouldn't catch a missing subtree.

Could you do this iteratively?

Yes — use two stacks (or queues) and zip-walk both trees, pushing children in lockstep. Same O(n) time, avoids recursion-depth issues on deep trees.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →