same_tree.py

from typing import Optional


class TreeNode:
    """LeetCode provides this class; repeated here so the file runs standalone."""

    def __init__(self, val: int = 0, left: "Optional[TreeNode]" = None,
                 right: "Optional[TreeNode]" = None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """LeetCode #100 - Same Tree (Easy)
    https://leetcode.com/problems/same-tree/

    Two binary trees are the same when they have identical structure *and*
    identical values in every corresponding position.
    """

    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        """Recursive comparison, walking both trees in lockstep.

        Key insight: "same tree" is defined recursively - the roots must match
        and both pairs of subtrees must match - so the code is the definition.

        The order of the base cases is what matters here:
          1. both empty        -> equal, nothing left to compare;
          2. exactly one empty -> different *shape*, so unequal;
          3. values differ     -> unequal.
        Collapsing 1 and 2 into one check is the usual bug: `p is None` alone
        would crash on `q.val` when q is a real node.

        `and` short-circuits, so a mismatch deep in the left subtree stops the
        right one from being explored at all.

        Time:  O(n) - n = size of the smaller tree; we stop at the first mismatch.
        Space: O(h) - recursion depth.
        """
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False

        return (self.isSameTree(p.left, q.left)
                and self.isSameTree(p.right, q.right))