Check if two binary trees are the same

Walk both trees together, node by node, confirming every structure and value lines up.

The idea

Two trees are the same only if every position matches: both nodes are null, or both exist with equal values and equal left and right subtrees. Compare the two roots, and if they match, recursively compare their left children to each other and their right children to each other. A single mismatch anywhere, in either structure or value, makes the whole comparison false.

Code

public static bool IsSameTree(TreeNode p, TreeNode q) {
    if (p == null && q == null) return true;
    if (p == null || q == null || p.val != q.val) return false;
    return IsSameTree(p.left, q.left) && IsSameTree(p.right, q.right);
}

Tips

• Checking "both null" and "exactly one null" first avoids ever reading .val off a null node.

In the .NET library

The same pairwise-recursion pattern (walk two trees together instead of one) also drives the mirror comparison in a symmetry check, with the right side compared against the left instead of itself.