Same Tree

Same Tree is a recursive binary tree problem. The question is whether two trees have exactly the same shape and the same value at every matching node.

The pattern is small but important: compare the current nodes first, then recursively compare the left subtrees and right subtrees.

Problem

Given the roots of two binary trees p and q, return true if the trees are the same.

Two trees are the same when:

• both are empty
• both have the same root value
• both left subtrees are the same
• both right subtrees are the same

Example:

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

result = true

Different shape example:

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

result = false

First Attempt

public boolean isSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null) return false;

    return (p.val == q.val)
            && isSameTree(p.left, q.left)
            && isSameTree(p.right, q.right);
}

This is already the right solution.

The key is the order of checks. Handle null first, then compare values, then recurse into children.

Clean Version

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }

        if (p == null || q == null) {
            return false;
        }

        return p.val == q.val
                && isSameTree(p.left, q.left)
                && isSameTree(p.right, q.right);
    }
}

LeetCode provides the TreeNode class:

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;
    }
}

Base Cases

There are three useful cases to remember.

Both nodes are missing:

if (p == null && q == null) {
    return true;
}

This means both trees ended at the same place.

One node is missing:

if (p == null || q == null) {
    return false;
}

This means the shapes are different.

Both nodes exist:

return p.val == q.val
        && isSameTree(p.left, q.left)
        && isSameTree(p.right, q.right);

This compares the current value and both child branches.

Why The Recursion Works

Each call answers one smaller version of the same question:

Are these two current nodes the same tree?

If the current nodes match, the answer depends on two smaller questions:

Are the left subtrees the same?
Are the right subtrees the same?

The && operator also short-circuits. If the values differ, Java does not need to keep checking the children.

Walkthrough

Input:

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

Every matching branch returns true, so the whole tree comparison returns true.

Complexity

n is the number of nodes visited, and h is the height of the recursion stack.

For a balanced tree, space is O(log n). For a skewed tree, space can become O(n).

Takeaways

• Binary tree equality is naturally recursive.
• Check null cases before reading p.val or q.val.
• Compare current value, then left subtree, then right subtree.
• Recursion stack space depends on tree height.