"""
p13 — Same Tree
================
LeetCode 100 · Easy · Topics: Tree, DFS, BFS

Sections:
  1. TreeNode + build_tree / random_tree / clone_tree
  2. is_same_recursive  — explicit four-case parallel recursion
  3. is_same_iterative  — single queue of (a, b) pairs
  4. stress_test        — clones expect True; mutated clones expect False
  5. edge_cases
"""

import random
import sys
from collections import deque
from typing import List, Optional, Tuple

sys.setrecursionlimit(10_000)


class TreeNode:
    __slots__ = ("val", "left", "right")

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


# ----------------------------------------------------------------------
# 2. RECURSIVE — explicit four-case parallel walk
# ----------------------------------------------------------------------
def is_same_recursive(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    # Case 1: both vacuous → equal.
    if p is None and q is None:
        return True
    # Cases 2 & 3: exactly one None → structure differs.
    if p is None or q is None:
        return False
    # Case 4: both non-None → values must match AND subtrees must match.
    # Short-circuit: value check first (cheapest), then left, then right.
    return (
        p.val == q.val
        and is_same_recursive(p.left, q.left)
        and is_same_recursive(p.right, q.right)
    )


# ----------------------------------------------------------------------
# 3. ITERATIVE — single queue of node-pairs
# ----------------------------------------------------------------------
def is_same_iterative(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    queue: deque = deque([(p, q)])
    while queue:
        a, b = queue.popleft()
        if a is None and b is None:
            continue
        if a is None or b is None or a.val != b.val:
            return False
        queue.append((a.left, b.left))
        queue.append((a.right, b.right))
    return True


# ----------------------------------------------------------------------
# Helpers
# ----------------------------------------------------------------------
def build_tree(values: List[Optional[int]]) -> Optional[TreeNode]:
    if not values or values[0] is None:
        return None
    root = TreeNode(values[0])
    q: deque = deque([root])
    i = 1
    n = len(values)
    while q and i < n:
        cur = q.popleft()
        if i < n and values[i] is not None:
            cur.left = TreeNode(values[i])
            q.append(cur.left)
        i += 1
        if i < n and values[i] is not None:
            cur.right = TreeNode(values[i])
            q.append(cur.right)
        i += 1
    return root


def clone_tree(node: Optional[TreeNode]) -> Optional[TreeNode]:
    if node is None:
        return None
    return TreeNode(node.val, clone_tree(node.left), clone_tree(node.right))


def random_tree(rng: random.Random, max_nodes: int = 30) -> Optional[TreeNode]:
    n = rng.randint(0, max_nodes)
    if n == 0:
        return None
    values: List[Optional[int]] = [rng.randint(-100, 100)]
    for _ in range(n - 1):
        values.append(None if rng.random() < 0.3 else rng.randint(-100, 100))
    return build_tree(values)


def list_nodes(node: Optional[TreeNode]) -> List[TreeNode]:
    """Flat list of all non-None nodes in the tree."""
    out: List[TreeNode] = []
    if node is None:
        return out
    stack = [node]
    while stack:
        cur = stack.pop()
        out.append(cur)
        if cur.left is not None:
            stack.append(cur.left)
        if cur.right is not None:
            stack.append(cur.right)
    return out


# ----------------------------------------------------------------------
# 4. STRESS TEST
# ----------------------------------------------------------------------
def stress_test(iterations: int = 1000) -> None:
    rng = random.Random(42)
    # Part A: clones must be equal under both implementations.
    for _ in range(iterations):
        t = random_tree(rng)
        c = clone_tree(t)
        r = is_same_recursive(t, c)
        i = is_same_iterative(t, c)
        assert r is True and i is True, f"clones not equal: rec={r} iter={i}"

    # Part B: mutate one node — must be unequal.
    mutated = 0
    while mutated < iterations:
        t = random_tree(rng)
        nodes = list_nodes(t)
        if not nodes:
            continue
        c = clone_tree(t)
        c_nodes = list_nodes(c)
        # Mutate one node's value to something different.
        idx = rng.randrange(len(c_nodes))
        c_nodes[idx].val = c_nodes[idx].val + 1
        r = is_same_recursive(t, c)
        i = is_same_iterative(t, c)
        assert r is False and i is False, f"mutation not detected: rec={r} iter={i}"
        mutated += 1

    print(f"stress_test PASSED — {iterations} clone-equal + {iterations} mutated-unequal")


# ----------------------------------------------------------------------
# 5. EDGE CASES
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases: List[Tuple[List[Optional[int]], List[Optional[int]], bool, str]] = [
        ([], [], True, "both empty"),
        ([1], [], False, "single vs empty"),
        ([], [1], False, "empty vs single"),
        ([1], [1], True, "single equal"),
        ([1], [2], False, "single values differ"),
        ([1, 2, 3], [1, 2, 3], True, "identical small"),
        ([1, 2], [1, None, 2], False, "structure differs"),
        ([1, 2, 1], [1, 1, 2], False, "values differ at children"),
    ]
    for a, b, expected, label in cases:
        ta, tb = build_tree(a), build_tree(b)
        rec = is_same_recursive(ta, tb)
        it = is_same_iterative(ta, tb)
        ok = rec == expected and it == expected
        print(f"  [{'PASS' if ok else 'FAIL'}] {label}: expected={expected} rec={rec} iter={it}")


if __name__ == "__main__":
    print("=== Edge cases ===")
    edge_cases()
    print("\n=== Stress test ===")
    stress_test()