50.Same Tree

EasyBlind 75Trees · 5/15

Problem

Given the roots of two binary trees p and q, return true if they are the same tree: structurally identical, with equal values in every corresponding node. Otherwise return false.

Examples

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

Input:  p = [1,2], q = [1,null,2]
Output: false
Explanation: Same values, but 2 is a left child in p and a right child in q.

Input:  p = [1,2,1], q = [1,1,2]
Output: false
Explanation: Same shape, but the children's values are swapped.

Constraints

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

💡 Key Insight

Two trees are equal exactly when their roots match and their left subtrees are equal and their right subtrees are equal. Walk both trees in lock-step and compare node pairs; the first mismatch (one node null and the other not, or different values) proves they differ.

Serialize and Compare

TimeO(n + m)SpaceO(n + m)

Intuition

If we write each tree as a string that captures both values and structure, equal trees produce equal strings. A pre-order traversal that also records null children (e.g. as #) uniquely identifies a binary tree, so comparing the two strings answers the question.

Algorithm

Serialize p with pre-order DFS, appending each value followed by a comma and #, for every null.
Serialize q the same way.
Return whether the two strings are equal.

Visualization

p = [1,2]       -> "1,2,#,#,#,"
q = [1,null,2]  -> "1,#,2,#,#,"
strings differ at position 2 -> false

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        StringBuilder a = new StringBuilder();
        StringBuilder b = new StringBuilder();
        serialize(p, a);
        serialize(q, b);
        return a.toString().equals(b.toString());
    }

    // pre-order with explicit null markers encodes structure as well as values
    private void serialize(TreeNode node, StringBuilder sb) {
        if (node == null) {
            sb.append("#,");
            return;
        }
        sb.append(node.val).append(',');
        serialize(node.left, sb);
        serialize(node.right, sb);
    }
}

Complexity

Time: O(n + m) — both trees are fully serialized, even if they differ at the root.
Space: O(n + m) — the two strings.

Iterative BFS on Node Pairs

TimeO(min(n, m))SpaceO(min(n, m))

Intuition

Instead of building strings, compare node pairs directly. Put (p, q) in a queue; each time a pair is polled, check it, then enqueue the pair of left children and the pair of right children. This stops at the first mismatch.

Algorithm

Enqueue the pair (p, q).
While the queue is not empty, poll (a, b):
- If both are null, continue.
- If exactly one is null, or a.val != b.val, return false.
- Enqueue (a.left, b.left) and (a.right, b.right).
Return true.

Visualization

p = [1,2,1], q = [1,1,2]

poll (1,1)  equal -> enqueue (2,1), (1,2)
poll (2,1)  2 != 1 -> return false

Code

java

import java.util.LinkedList;
import java.util.Queue;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        // LinkedList allows null elements (ArrayDeque does not)
        Queue<TreeNode[]> queue = new LinkedList<>();
        queue.offer(new TreeNode[] {p, q});
        while (!queue.isEmpty()) {
            TreeNode[] pair = queue.poll();
            TreeNode a = pair[0];
            TreeNode b = pair[1];
            if (a == null && b == null) {
                continue;
            }
            if (a == null || b == null || a.val != b.val) {
                return false;
            }
            queue.offer(new TreeNode[] {a.left, b.left});
            queue.offer(new TreeNode[] {a.right, b.right});
        }
        return true;
    }
}

Complexity

Time: O(min(n, m)) — we stop at the first mismatch, and never go past the smaller tree.
Space: O(min(n, m)) — the queue holds at most one level's worth of pairs.

Recursive DFSOptimal

TimeO(min(n, m))SpaceO(min(h1, h2))

Intuition

The recursive definition is the cleanest form: two null trees are equal; a null and a non-null are not; otherwise the roots' values must match and both pairs of subtrees must be the same tree. Short-circuit && stops as soon as one side fails.

Algorithm

If p and q are both null, return true.
If exactly one is null, or p.val != q.val, return false.
Return isSameTree(p.left, q.left) && isSameTree(p.right, q.right).

Dry Run

flowchart TD
    A["compare (1, 1)<br/>values equal"] --> B["compare left (2, 2)<br/>values equal"]
    A --> C["compare right (3, 3)<br/>values equal"]
    B --> B1["(null, null) -> true"]
    B --> B2["(null, null) -> true"]
    C --> C1["(null, null) -> true"]
    C --> C2["(null, null) -> true"]
    A --> R["all true -> return true"]

Code

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true; // both subtrees ended at the same place
        }
        if (p == null || q == null || p.val != q.val) {
            return false; // shape or value mismatch
        }
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

Complexity

Time: O(min(n, m)) — each pair of corresponding nodes is compared at most once.
Space: O(min(h1, h2)) — recursion depth; O(n) in the worst (skewed) case.

Complexity Comparison

Approach	Time	Space
Serialize and Compare	O(n + m)	O(n + m)
Iterative BFS on Node Pairs	O(min(n, m))	O(min(n, m))
Recursive DFS	O(min(n, m))	O(min(h1, h2))

Common Pitfalls

Comparing only traversal values without null markers — [1,2] and [1,null,2] produce the same pre-order 1,2 but are different trees.
Checking p.val != q.val before the null checks, which throws a NullPointerException.
Using ArrayDeque to store null children — it rejects null elements; wrap pairs in an array or use LinkedList.
Comparing nodes with p == q (reference equality) — the trees are separate objects, so you must compare val.