100. Same Tree

Time: O(n)

Space: O(h)

Intuition

Two binary trees are the same if and only if their roots hold the same value AND their left subtrees are the same AND their right subtrees are the same. This directly translates to a recursive definition with simple base cases.

Algorithm

1Base case: if both nodes are null -> return true (two empty trees are identical).
2Base case: if one is null and the other is not -> return false.
3Base case: if root values differ -> return false.
4Recurse: return IsSameTree(p.left, q.left) AND IsSameTree(p.right, q.right).

Example Walkthrough

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

1.Compare roots: both 1 -> match. Recurse on left children (both 2) and right children (both 3).
2.Left: both 2 -> match. Their children are null -> base case, return true.
3.Right: both 3 -> match. Their children are null -> base case, return true.
4.All checks pass -> return true.

Output: true

Common Pitfalls

•Check for null before comparing values - accessing .val on null causes a NullReferenceException.
•The null check `p == null && q == null` must come before `p == null || q == null` to avoid false negatives.

100.cs

// Approach: Recursively compare both trees node by node.
// Base cases: both nodes null means identical; one null or mismatched values means not identical.
// A subtree is the same only if both its left and right subtrees are identical.
// Every node is visited exactly once — O(n) time. Recursion depth equals tree height O(h).
// Time: O(n) Space: O(h)

public class TreeNode
{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null)
    {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution
{
    public bool IsSameTree(TreeNode p, TreeNode q)
    {
        if (p == null || q == null)
            return (p == q);

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

Was this solution helpful?