parikshan

same-tree

Difficulty: Easy  ·  Topic: Trees  ·  Practice it on parikshan: /practice/same-tree/start

The story

A static-site generator at a documentation tool compares the previous build's HTML against the current build's HTML to decide which pages to push to the CDN. Both pages have already been parsed into DOM trees. If the trees are structurally identical with the same text content at every position, the page is unchanged and the cached copy stays put. If they differ anywhere, the new version uploads. Comparing strings is fragile (whitespace, attribute order, formatter drift); comparing tree structure is exact. The diff has to be fast enough to run on tens of thousands of pages per build.

That is same-tree. Once you see this problem in this framing, you will recognise it in every system that asks "is this hierarchical thing exactly what we had before?": AST equality checks, JSON-document diffs, config-file comparisons, test-snapshot validators.

What's actually being asked

Given two binary trees, decide whether they are structurally identical AND have the same value at every corresponding position. Return true or false. The empty tree is equal only to the empty tree.

The naive approach

Serialise each tree to a string (say, level-order with null markers) and compare strings. That works and is O(n). The catch is that you cannot short-circuit on the first difference; you build the entire serialisation of both trees before noticing. For trees of 10⁴ nodes that means two O(n) walks plus an O(n) string allocation, even when the trees differ at the root. The naive answer is correct but wastes memory and obscures the algorithm.

A second naive trap is comparing two in-order traversals only. That gives equal traversals for some unequal trees (a balanced and a skewed tree with the same set of values can have the same in-order sequence). One traversal does not determine a tree; you need two (pre+in, or post+in) to reconstruct.

The key insight

Equality of trees is recursive in the same shape the trees themselves are: two trees are equal if and only if both are empty, or their roots have the same value AND the left subtrees are equal AND the right subtrees are equal. That recurrence is two empty bases, one structural mismatch base, and one recursive case. Four lines of logic, total.

The algorithm walks both trees in lockstep. As soon as a mismatch is found at any position, return false; no more work. That short-circuiting is what makes the runtime O(min(n, m)) rather than O(n) in practice: on inputs that differ early, the walk stops early.

Step-by-step approach

  1. Parse both inputs into trees. An empty line falls back to [], which builds the empty tree.
  2. Define same(a, b):
    • If a is None and b is None, return true.
    • If exactly one of a, b is None, return false.
    • If a.val != b.val, return false.
    • Return same(a.left, b.left) AND same(a.right, b.right).
  3. Print same(rootA, rootB).

For 10⁴-node skewed inputs, walk iteratively with a stack of (a, b) pairs. Push the two roots; on each pop apply the base cases and push the four child pairs. Short-circuit on the first false.

Worked example

Tree A: [1, 2, 3]            Tree B: [1, 2, 3]
   1                              1
  / \                            / \
 2   3                          2   3

same(rootA, rootB):
  values 1 == 1
  same(2, 2):
    values 2 == 2
    same(None, None) -> true
    same(None, None) -> true
  same(3, 3):
    similar -> true
  return true

Second example, structure mismatch:

Tree A: [1, 2]               Tree B: [1, null, 2]
   1                              1
  /                                \
 2                                  2

same(rootA, rootB):
  values 1 == 1
  same(2, None) -> exactly one None -> false

Answer: false. The walk stops at the first mismatch.

Complexity

  • Time: O(min(n, m)) in the best case (early divergence), O(min(n, m)) in the worst case (identical to the smaller tree). Either way bounded by the smaller tree.
  • Space: O(min(h_a, h_b)) for the stack.

You cannot do better: in the worst case (both trees actually equal) you have to look at every node to confirm it.

Common pitfalls

  • Wrong base case order: check both-None before one-None. If you write if a.val != b.val first, you get an AttributeError when one is None.
  • Comparing by traversal alone: two trees with the same pre-order are not necessarily equal; you need the structural nulls too.
  • Equating None == None to False in some languages: in Python None == None is True, but if your language has nullable references with three-valued logic, double-check.
  • Skipping the parse-empty-line case: the spec allows either tree to be []. The starter code guards (raw[i] or '[]') so an empty string falls back; if you write your own input handling, replicate that guard.

Where this shows up in the enterprise

  • DOM diffing in React, Vue, Svelte: every framework's reconciler is essentially a tree-equality test that, when it finds a difference, also returns enough information to patch. The equality test on type and key is same-tree on a per-node basis.
  • TypeScript compiler incremental builds: the compiler compares the AST of a re-parsed file against its cached AST to decide whether to reuse type information. The comparison is structural same-tree.
  • Jest, Vitest, Playwright snapshot tests: snapshots are trees of expected DOM or component output; comparing actual to expected is a same-tree check with detailed mismatch reporting.
  • PostgreSQL plan caching: query plans are trees; the planner reuses a cached plan when the new parse tree is structurally identical to the cached version.
  • MongoDB aggregation pipeline caching: pipelines are trees of stages; identity is the cache key.
  • Babel and ESLint rule engines: linting rules match AST subtree patterns; the pattern matcher under the hood is same-tree against a wildcarded template.
  • Git's git diff-tree: the underlying object model is a Merkle tree; comparing two trees for equality is the foundation of every diff operation.

The pattern is universal: any time two hierarchies need to be compared exactly, you are running same-tree.

Variants you'll see elsewhere

  • subtree-of-another-tree: is tree A a subtree of tree B? Equivalent to "for some node u in B, same(A, u) is true".
  • flip-equivalent-binary-trees: are two trees equal up to subtree swaps?
  • merge-two-binary-trees: produces a third tree by overlaying. Same lockstep walk, different combine step.
  • binary-tree-tilt and similar aggregations: same parallel-walk shape over two trees.
  • Structural hashing for Merkle trees: hash each subtree, compare hashes. Probabilistic equality, same-tree without traversal once the hashes are built.

How parikshan turns this into a learning loop

After you read this article and click through to the practice link, the parikshan flow integrates four layers:

  1. The editor runs your code against public tests and per-session dynamic private tests. The dynamic tests include pairs where the trees differ only at a deep node, to verify your walk does not allocate intermediate structures of size O(n). They also include [] vs [], [] vs [1], and other empty-tree edge cases.
  2. Hints are graduated. The first hint asks you to write the recurrence in English; the third gives you the lockstep stack. Each costs integrity.
  3. The AI training assistant offers Explain, Review, Find Bugs, Add Comments, Optimise in exam mode at a small integrity cost each; free-form chat in practice mode.
  4. The dispute flow runs after the verdict. The common dispute on same-tree is candidates who serialised both trees, hit a slight encoding mismatch, and are convinced the test data is buggy. The reviewer can confirm the encoding contract.

Read the concept, attempt in practice mode, take hints when stuck, then redo in exam mode with no help. When you can write the four-line recurrence in under three minutes without touching AI, the pattern is in your fingers.

In the AI-integrated workspace

In your future job, you will not write same-tree by hand. An agent will. Your job is to:

  1. Recognise that "are these two hierarchies identical" is a lockstep parallel walk, not a serialise-and-compare.
  2. Tell the agent precisely: "iterative lockstep with a stack of pairs, short-circuit on the first mismatch, base cases are both-None, one-None, values differ".
  3. Read the agent's code and check the base case order (both-None before one-None) and confirm the recursion descends into corresponding children, not crossed children (that would be symmetric-tree).
  4. Stress-test on the edge cases the agent will silently miss: both empty, one empty, single-node values differ, [1,2] vs [1,null,2].

Candidates who can name "this is same-tree, lockstep walk" within five seconds are the ones who direct AI agents productively. Candidates who cannot recognise the pattern end up approving a 40-line serialise-and-compare that allocates twice the necessary memory and silently passes the sample. parikshan is built to train the first kind.