Same Tree

EasyTrees · DFS🧩 Tree DFS LeetCode #100 ↗Updated Oct 30, 2026

Problem

You are handed the roots p and q of two binary trees. Decide whether they are identical: the two trees must have exactly the same shape, and every pair of nodes sitting in the same position must carry the same value.

Inputp = [1,2,3], q = [1,2,3]Outputtrue

Inputp = [1,2], q = [1,null,2]Outputfalse

Inputp = [1,2,1], q = [1,1,2]Outputfalse

0 ≤ nodes in each tree ≤ 100 · -10⁴ ≤ Node.val ≤ 10⁴

Try it yourself

Java

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Two trees are equal exactly when their roots match and the left subtrees are equal and the right subtrees are equal. Walk both trees in lockstep and stop at the first mismatch — shape (null vs non-null) or value.

PatternTree DFS

Instinct If the answer for a node can be built from the answers of its left and right subtrees, write one recursive function and trust it on the children.

Memory hack Ask the kids, then decide - each child reports up, the parent combines, and a global variable keeps the best "bend" seen so far.

Open the Tree DFS guide →

Approaches

Brute ForceSerialize Both Trees & Compare

Time O(n + m)Space O(n + m)

Write each tree as a pre-order string that also records every missing child with a # marker. Thanks to the null markers the encoding is unique, so two trees are identical exactly when their strings are equal.

Java

public boolean isSameTree(TreeNode p, TreeNode q) {
    StringBuilder a = new StringBuilder(), b = new StringBuilder();
    encode(p, a);
    encode(q, b);
    return a.toString().equals(b.toString());
}
private void encode(TreeNode node, StringBuilder sb) {
    if (node == null) {
        sb.append(",#"); // null marker keeps the shape unambiguous
        return;
    }
    sb.append(',').append(node.val);
    encode(node.left, sb);
    encode(node.right, sb);
}

Correct and easy to trust, but always walks both trees fully and builds two strings.

OptimalLockstep Recursive DFS

Time O(min(n, m))Space O(min(h_p, h_q))

Compare the two current nodes: both null means this branch matches; exactly one null, or different values, means a mismatch. Otherwise recurse on the two left children and the two right children. The && short-circuits, so the walk ends at the first difference and never goes deeper than the shorter tree.

Java

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false; // shapes differ
    if (p.val != q.val) return false;
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}

No extra buffers, early exit, and the base case of many tree-comparison problems.

Pro tip

An iterative version pushes (p, q) pairs on a stack/queue; useful if the interviewer worries about recursion depth on very deep trees.

At a glance

Level	Approach	Time	Space
Brute Force	Serialize Both Trees & Compare	`O(n + m)`	`O(n + m)`
Optimal	Lockstep Recursive DFS	`O(min(n, m))`	`O(min(h_p, h_q))`

Common pitfalls

Checking p.val before ruling out a null node → NullPointerException.
Comparing only in-order (or any single) traversal without null markers — different shapes can give the same sequence.
Serializing without a separator: values 1,23 and 12,3 both become 123.

Interview tips

Spell out the three base cases (both null, one null, values differ) before writing code.
Mention that a shape-plus-value check is reused by Subtree of Another Tree (572) and Symmetric Tree (101).
State complexity in terms of the smaller tree — the walk stops once either side runs out.

Pattern

Paired DFS → whenever two trees (or two halves of one tree) must be compared position by position.

My notes saved in this browser