Workspace Code & DSA
Learning pathsPricingA
← DSA problem library

DSA-079 · Match ordered child positions, nullness, and values

Same Tree

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 108019 deterministic checks. Learner drafts are not executed.

Understand the problem

Return whether two binary trees have the same ordered shape and equal values at every corresponding position.

  • Input roots are null or finite proper binary trees with at most 100,000 nodes per tree: no cycles and no shared child within one tree. Values span the full int domain. Structure/size are preconditions, not an extra validation traversal.
  • Preserve every original value, node identity, and left/right edge. Compact level-order arrays in examples are adapters, consuming two child slots per nonnull queued parent; they are not heap-indexed arrays.
  • The two inputs may be the same root or may share objects across the two trees; each individual input must still be proper. Equality compares structure and values, not whether corresponding references are the same object. Empty/empty is true; exactly one empty is false.

Examples

  1. Input: a=[1,2,3], b=[1,2,3]
    Output: true

    Independent allocations can be equal trees.

  2. Input: a=[1,2], b=[1,null,2]
    Output: false

    The values occur on different child sides; traversal values without null positions are insufficient.

Before you start

  • Null child positions and proper tree structure
  • Explicit stacks of corresponding reference pairs

Recognize the structure

Every pending pair represents the same root-relative L/R position in the two trees. A mismatch at one such position is a complete counterexample; matching preorder values without null markers is not enough.

Try before revealing

Hint 1

A node value alone does not describe its position.

Hint 2

A comparison item should contain one reference from each input.

Hint 3

Reject null/value mismatches; otherwise queue matching left/left and right/right pairs.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Recursive corresponding-subtree comparison

If either root is null, require both null. Otherwise compare values, then left with left and right with right. For [1,2] versus [1,null,2], roots match but the left-child pair has only one node, so comparison fails. Explicit pair frames preserve this logic while supporting deep trees.

Improve the baseline

Represent nullable pairs safely

An ArrayDeque entry is a nonnull Pair object whose a/b fields may be null. This permits exact null-position comparisons without putting null directly in the deque.

Reject the first witness

When exactly one field is null or nonnull values differ, return false. A pair of nulls is satisfied and needs no expansion.

Expand only matching positions

Push right/right then left/left for matching nonnull values. Once all pairs are discharged, no position can differ.

Why it is correct

Pair meaning

Initially the root pair denotes the empty path in both inputs. Expanding a matching pair adds the same L or R suffix on both sides.

Sound rejection

Unequal nullness or values at a corresponding path violates the definition of equal trees, so returning false is justified.

Complete success

Every reachable position is expanded or matched as null. A finite proper structure makes pending work terminate; if no rejection occurs, all positions and values match.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    public static final class Node {
        public final int value;
        public Node left, right;
        public Node(int value) { this.value = value; }
    }
    private record Pair(Node a, Node b) {}
    public static boolean same(Node a, Node b) {
        ArrayDeque<Pair> pending = new ArrayDeque<>();
        pending.push(new Pair(a,b));
        while (!pending.isEmpty()) {
            Pair pair = pending.pop();
            if (pair.a == null || pair.b == null) {
                if (pair.a != pair.b) return false;
                continue;
            }
            if (pair.a.value != pair.b.value) return false;
            pending.push(new Pair(pair.a.right,pair.b.right));
            pending.push(new Pair(pair.a.left,pair.b.left));
        }
        return true;
    }
    public static boolean baseline(Node a, Node b) {
        if (a == null || b == null) return a == b;
        return a.value == b.value && baseline(a.left,b.left) && baseline(a.right,b.right);
    }
}

Read the meaningful blocks

A wrapper may contain null fields

Deque null rejection applies to the Pair entry, not its fields.

Handle nullness before reading values

Dereferencing either field before the null branch breaks valid empty inputs.

No identity equality shortcut is required

The algorithm remains correct for independent copies and overlapping inputs because it reads without mutation.

Complexity

Worst-case time is O(n+m) for the two trees; it may stop earlier at the first mismatch. For matching shapes, each corresponding node/null position is checked once. The DFS pair frontier has O(h) worst-case auxiliary space, using the larger input height.

The recursive baseline has the same work and O(h) call-stack cost but is limited to shallow tests. Flattening to an encoding adds O(n+m) storage and is unnecessary for a boolean comparison.

Exact-state walkthroughs

Reveal normal and boundary traces

Independent equal trees with duplicates

Input: {"a":[1,2,2],"b":[1,2,2]} · Result: true

Step 1 of 9: Create nullable comparison pairs.

A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.

Same Tree — matching ordered positions

Phase: initial.

Original objects — unchanged source edges

  • A0: 1left → A1right → A2
  • A1: 2left → nullright → null
  • A2: 2left → nullright → null
  • B0: 1left → B1right → B2
  • B1: 2left → nullright → null
  • B2: 2left → nullright → null

Current pair: null ↔ null. Children are paired left/left and right/right.

Nullable pairs — stack top at right

  • A0 ↔ B0

Null positions participate in comparison. Equal values do not replace shape checks; a rejected pair leaves later work unprocessed.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
VariableValue
treeNodes[{"id":"A0","value":1,"left":"A1","right":"A2"},{"id":"A1","value":2,"left":null,"right":null},{"id":"A2","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":"B1","right":"B2"},{"id":"B1","value":2,"left":null,"right":null},{"id":"B2","value":2,"left":null,"right":null}]
pending[{"a":"A0","b":"B0"}]
checked[]
mode"same positions"
phase"initial"
pairnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Pair(Node a, Node b) {}
 9     public static boolean same(Node a, Node b) {
10         ArrayDeque<Pair> pending = new ArrayDeque<>();
11         pending.push(new Pair(a,b));
12         while (!pending.isEmpty()) {
13             Pair pair = pending.pop();
14             if (pair.a == null || pair.b == null) {
15                 if (pair.a != pair.b) return false;
16                 continue;
17             }
18             if (pair.a.value != pair.b.value) return false;
19             pending.push(new Pair(pair.a.right,pair.b.right));
20             pending.push(new Pair(pair.a.left,pair.b.left));
21         }
22         return true;
23     }
24     public static boolean baseline(Node a, Node b) {
25         if (a == null || b == null) return a == b;
26         return a.value == b.value && baseline(a.left,b.left) && baseline(a.right,b.right);
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Create nullable comparison pairs.

    A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":"A2"},{"id":"A1","value":2,"left":null,"right":null},{"id":"A2","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":"B1","right":"B2"},{"id":"B1","value":2,"left":null,"right":null},{"id":"B2","value":2,"left":null,"right":null}]
    pending
    [{"a":"A0","b":"B0"}]
    checked
    []
    mode
    "same positions"
    phase
    "initial"
    pair
    null
  2. Discharge this pair and expand only matching nonnull positions.

    Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":"A2"},{"id":"A1","value":2,"left":null,"right":null},{"id":"A2","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":"B1","right":"B2"},{"id":"B1","value":2,"left":null,"right":null},{"id":"B2","value":2,"left":null,"right":null}]
    pending
    [{"a":"A2","b":"B2"},{"a":"A1","b":"B1"}]
    checked
    [{"a":"A0","b":"B0","matches":true}]
    mode
    "same positions"
    phase
    "match"
    pair
    {"a":"A0","b":"B0"}
  3. Discharge this pair and expand only matching nonnull positions.

    Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":"A2"},{"id":"A1","value":2,"left":null,"right":null},{"id":"A2","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":"B1","right":"B2"},{"id":"B1","value":2,"left":null,"right":null},{"id":"B2","value":2,"left":null,"right":null}]
    pending
    [{"a":"A2","b":"B2"},{"a":null,"b":null},{"a":null,"b":null}]
    checked
    [{"a":"A0","b":"B0","matches":true},{"a":"A1","b":"B1","matches":true}]
    mode
    "same positions"
    phase
    "match"
    pair
    {"a":"A1","b":"B1"}
  4. Discharge this pair and expand only matching nonnull positions.

    Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":"A2"},{"id":"A1","value":2,"left":null,"right":null},{"id":"A2","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":"B1","right":"B2"},{"id":"B1","value":2,"left":null,"right":null},{"id":"B2","value":2,"left":null,"right":null}]
    pending
    [{"a":"A2","b":"B2"},{"a":null,"b":null}]
    checked
    [{"a":"A0","b":"B0","matches":true},{"a":"A1","b":"B1","matches":true},{"a":null,"b":null,"matches":true}]
    mode
    "same positions"
    phase
    "both-null"
    pair
    {"a":null,"b":null}
  5. Discharge this pair and expand only matching nonnull positions.

    Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":"A2"},{"id":"A1","value":2,"left":null,"right":null},{"id":"A2","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":"B1","right":"B2"},{"id":"B1","value":2,"left":null,"right":null},{"id":"B2","value":2,"left":null,"right":null}]
    pending
    [{"a":"A2","b":"B2"}]
    checked
    [{"a":"A0","b":"B0","matches":true},{"a":"A1","b":"B1","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true}]
    mode
    "same positions"
    phase
    "both-null"
    pair
    {"a":null,"b":null}
  6. Discharge this pair and expand only matching nonnull positions.

    Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":"A2"},{"id":"A1","value":2,"left":null,"right":null},{"id":"A2","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":"B1","right":"B2"},{"id":"B1","value":2,"left":null,"right":null},{"id":"B2","value":2,"left":null,"right":null}]
    pending
    [{"a":null,"b":null},{"a":null,"b":null}]
    checked
    [{"a":"A0","b":"B0","matches":true},{"a":"A1","b":"B1","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true},{"a":"A2","b":"B2","matches":true}]
    mode
    "same positions"
    phase
    "match"
    pair
    {"a":"A2","b":"B2"}
  7. Discharge this pair and expand only matching nonnull positions.

    Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":"A2"},{"id":"A1","value":2,"left":null,"right":null},{"id":"A2","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":"B1","right":"B2"},{"id":"B1","value":2,"left":null,"right":null},{"id":"B2","value":2,"left":null,"right":null}]
    pending
    [{"a":null,"b":null}]
    checked
    [{"a":"A0","b":"B0","matches":true},{"a":"A1","b":"B1","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true},{"a":"A2","b":"B2","matches":true},{"a":null,"b":null,"matches":true}]
    mode
    "same positions"
    phase
    "both-null"
    pair
    {"a":null,"b":null}
  8. Discharge this pair and expand only matching nonnull positions.

    Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":"A2"},{"id":"A1","value":2,"left":null,"right":null},{"id":"A2","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":"B1","right":"B2"},{"id":"B1","value":2,"left":null,"right":null},{"id":"B2","value":2,"left":null,"right":null}]
    pending
    []
    checked
    [{"a":"A0","b":"B0","matches":true},{"a":"A1","b":"B1","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true},{"a":"A2","b":"B2","matches":true},{"a":null,"b":null,"matches":true},{"a":null,"b":null,"matches":true}]
    mode
    "same positions"
    phase
    "both-null"
    pair
    {"a":null,"b":null}
  9. Return the problem-specific identity, value, optional result, or round-trip observation.

    Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.

    result
    true

Same values, different child sides

Input: {"a":[1,2],"b":[1,null,2]} · Result: false

Step 1 of 4: Create nullable comparison pairs.

A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.

Same Tree — matching ordered positions

Phase: initial.

Original objects — unchanged source edges

  • A0: 1left → A1right → null
  • A1: 2left → nullright → null
  • B0: 1left → nullright → B1
  • B1: 2left → nullright → null

Current pair: null ↔ null. Children are paired left/left and right/right.

Nullable pairs — stack top at right

  • A0 ↔ B0

Null positions participate in comparison. Equal values do not replace shape checks; a rejected pair leaves later work unprocessed.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
VariableValue
treeNodes[{"id":"A0","value":1,"left":"A1","right":null},{"id":"A1","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":null,"right":"B1"},{"id":"B1","value":2,"left":null,"right":null}]
pending[{"a":"A0","b":"B0"}]
checked[]
mode"same positions"
phase"initial"
pairnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Pair(Node a, Node b) {}
 9     public static boolean same(Node a, Node b) {
10         ArrayDeque<Pair> pending = new ArrayDeque<>();
11         pending.push(new Pair(a,b));
12         while (!pending.isEmpty()) {
13             Pair pair = pending.pop();
14             if (pair.a == null || pair.b == null) {
15                 if (pair.a != pair.b) return false;
16                 continue;
17             }
18             if (pair.a.value != pair.b.value) return false;
19             pending.push(new Pair(pair.a.right,pair.b.right));
20             pending.push(new Pair(pair.a.left,pair.b.left));
21         }
22         return true;
23     }
24     public static boolean baseline(Node a, Node b) {
25         if (a == null || b == null) return a == b;
26         return a.value == b.value && baseline(a.left,b.left) && baseline(a.right,b.right);
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Create nullable comparison pairs.

    A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":null},{"id":"A1","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":null,"right":"B1"},{"id":"B1","value":2,"left":null,"right":null}]
    pending
    [{"a":"A0","b":"B0"}]
    checked
    []
    mode
    "same positions"
    phase
    "initial"
    pair
    null
  2. Discharge this pair and expand only matching nonnull positions.

    Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":null},{"id":"A1","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":null,"right":"B1"},{"id":"B1","value":2,"left":null,"right":null}]
    pending
    [{"a":null,"b":"B1"},{"a":"A1","b":null}]
    checked
    [{"a":"A0","b":"B0","matches":true}]
    mode
    "same positions"
    phase
    "match"
    pair
    {"a":"A0","b":"B0"}
  3. Reject an exact null-position or value mismatch.

    This corresponding position is a complete counterexample; remaining pending comparisons need not run.

    treeNodes
    [{"id":"A0","value":1,"left":"A1","right":null},{"id":"A1","value":2,"left":null,"right":null},{"id":"B0","value":1,"left":null,"right":"B1"},{"id":"B1","value":2,"left":null,"right":null}]
    pending
    [{"a":null,"b":"B1"}]
    checked
    [{"a":"A0","b":"B0","matches":true},{"a":"A1","b":null,"matches":false}]
    mode
    "same positions"
    phase
    "reject"
    pair
    {"a":"A1","b":null}
  4. Return the problem-specific identity, value, optional result, or round-trip observation.

    Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.

    result
    false

Both empty

Input: {"a":[],"b":[]} · Result: true

Step 1 of 3: Create nullable comparison pairs.

A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.

Same Tree — matching ordered positions

Phase: initial.

Original objects — unchanged source edges

Empty tree.

Current pair: null ↔ null. Children are paired left/left and right/right.

Nullable pairs — stack top at right

  • null ↔ null

Null positions participate in comparison. Equal values do not replace shape checks; a rejected pair leaves later work unprocessed.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
VariableValue
treeNodes[]
pending[{"a":null,"b":null}]
checked[]
mode"same positions"
phase"initial"
pairnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Pair(Node a, Node b) {}
 9     public static boolean same(Node a, Node b) {
10         ArrayDeque<Pair> pending = new ArrayDeque<>();
11         pending.push(new Pair(a,b));
12         while (!pending.isEmpty()) {
13             Pair pair = pending.pop();
14             if (pair.a == null || pair.b == null) {
15                 if (pair.a != pair.b) return false;
16                 continue;
17             }
18             if (pair.a.value != pair.b.value) return false;
19             pending.push(new Pair(pair.a.right,pair.b.right));
20             pending.push(new Pair(pair.a.left,pair.b.left));
21         }
22         return true;
23     }
24     public static boolean baseline(Node a, Node b) {
25         if (a == null || b == null) return a == b;
26         return a.value == b.value && baseline(a.left,b.left) && baseline(a.right,b.right);
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Create nullable comparison pairs.

    A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.

    treeNodes
    []
    pending
    [{"a":null,"b":null}]
    checked
    []
    mode
    "same positions"
    phase
    "initial"
    pair
    null
  2. Discharge this pair and expand only matching nonnull positions.

    Same Tree pairs equal side paths; Symmetric Tree crosses sides at every expansion. A null pair closes a position without adding children.

    treeNodes
    []
    pending
    []
    checked
    [{"a":null,"b":null,"matches":true}]
    mode
    "same positions"
    phase
    "both-null"
    pair
    {"a":null,"b":null}
  3. Return the problem-specific identity, value, optional result, or round-trip observation.

    Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.

    result
    true

Value mismatch at an extreme

Input: {"a":[-2147483648],"b":[2147483647]} · Result: false

Step 1 of 3: Create nullable comparison pairs.

A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.

Same Tree — matching ordered positions

Phase: initial.

Original objects — unchanged source edges

  • A0: -2147483648left → nullright → null
  • B0: 2147483647left → nullright → null

Current pair: null ↔ null. Children are paired left/left and right/right.

Nullable pairs — stack top at right

  • A0 ↔ B0

Null positions participate in comparison. Equal values do not replace shape checks; a rejected pair leaves later work unprocessed.

Cards are identity records, not level-order array indices or a spatial tree layout. Values can repeat. The complete exact state remains available in the table and static walkthrough.

State after this step
VariableValue
treeNodes[{"id":"A0","value":-2147483648,"left":null,"right":null},{"id":"B0","value":2147483647,"left":null,"right":null}]
pending[{"a":"A0","b":"B0"}]
checked[]
mode"same positions"
phase"initial"
pairnull
See the affected Java block
 1 import java.util.*;
 2 public final class Solution {
 3     public static final class Node {
 4         public final int value;
 5         public Node left, right;
 6         public Node(int value) { this.value = value; }
 7     }
 8     private record Pair(Node a, Node b) {}
 9     public static boolean same(Node a, Node b) {
10         ArrayDeque<Pair> pending = new ArrayDeque<>();
11         pending.push(new Pair(a,b));
12         while (!pending.isEmpty()) {
13             Pair pair = pending.pop();
14             if (pair.a == null || pair.b == null) {
15                 if (pair.a != pair.b) return false;
16                 continue;
17             }
18             if (pair.a.value != pair.b.value) return false;
19             pending.push(new Pair(pair.a.right,pair.b.right));
20             pending.push(new Pair(pair.a.left,pair.b.left));
21         }
22         return true;
23     }
24     public static boolean baseline(Node a, Node b) {
25         if (a == null || b == null) return a == b;
26         return a.value == b.value && baseline(a.left,b.left) && baseline(a.right,b.right);
27     }
28 }
29

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace
  1. Create nullable comparison pairs.

    A Pair wrapper is nonnull even when its fields represent absent children. Pending stack top is at the right.

    treeNodes
    [{"id":"A0","value":-2147483648,"left":null,"right":null},{"id":"B0","value":2147483647,"left":null,"right":null}]
    pending
    [{"a":"A0","b":"B0"}]
    checked
    []
    mode
    "same positions"
    phase
    "initial"
    pair
    null
  2. Reject an exact null-position or value mismatch.

    This corresponding position is a complete counterexample; remaining pending comparisons need not run.

    treeNodes
    [{"id":"A0","value":-2147483648,"left":null,"right":null},{"id":"B0","value":2147483647,"left":null,"right":null}]
    pending
    []
    checked
    [{"a":"A0","b":"B0","matches":false}]
    mode
    "same positions"
    phase
    "reject"
    pair
    {"a":"A0","b":"B0"}
  3. Return the problem-specific identity, value, optional result, or round-trip observation.

    Tree cards use object identities. Only inversion mutates a source; decoded nodes are fresh. Teaching histories are excluded from Java auxiliary-space claims.

    result
    false

Test the contract

  1. Input: null, null
    Output: true

    Both shapes are empty.

  2. Input: [1], null
    Output: false

    Only one root exists.

  3. Input: Equal values on opposite sides
    Output: false

    Ordered shape matters.

  4. Input: Separate equal 100,000-node chains
    Output: true

    Deep equality uses explicit pair frames.

Common mistakes and counterexamples

Compare only preorder values

Counterexample: [1,2] and [1,null,2] both emit 1,2 without null markers.

Compare paired child positions or include null structure in any encoding.

Require a==b for matching nodes

Counterexample: Two separately allocated [1] trees should compare true.

Use identity only for the both-null check; compare nonnull values and descendants.

Put null nodes directly into ArrayDeque

Counterexample: An empty child is a legitimate comparison position but a forbidden deque element.

Store a nonnull Pair wrapper.

Follow-ups

Return a first mismatch path.

Carry a compact parent-linked path or reconstruct it when rejecting. State traversal order so first mismatch is deterministic; copying full strings per frame can add O(nh) work.

Compare unordered binary trees.

Allowing left/right exchange changes the equivalence relation. Simple paired DFS is insufficient; use canonical subtree signatures or a carefully memoized equivalence algorithm, accounting for collisions if hashing.

Inputs are graphs with sharing.

Decide whether identity-sharing patterns must match or only unfolded values. Cycles need visited pair state and possibly a bijection, rather than this proper-tree contract.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

No unsaved text changes · 157/20,000 characters

Self-review

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.