"""
p15 — Symmetric Tree
====================
LeetCode 101 · Easy · Topics: Tree, DFS, BFS

The mirror-walk: parallel-walk with CROSS pairing.
Symmetric ⇔ invert(T) == T (the fixed point of the invert operator).

Sections:
  1. TreeNode + helpers + invert + is_same (reused)
  2. is_symmetric_recursive   — mirror-walk with cross pairing
  3. is_symmetric_iterative   — single queue of cross-paired pairs
  4. is_symmetric_via_invert  — uses invert + is_same
  5. stress_test              — symmetric expects True; mutated expects False
  6. 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 — mirror-walk with CROSS pairing
# ----------------------------------------------------------------------
def is_symmetric_recursive(root: Optional[TreeNode]) -> bool:
    def is_mirror(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
        if a is None and b is None:
            return True
        if a is None or b is None:
            return False
        return (
            a.val == b.val
            and is_mirror(a.left, b.right)   # CROSS
            and is_mirror(a.right, b.left)   # CROSS
        )

    if root is None:
        return True
    return is_mirror(root.left, root.right)


# ----------------------------------------------------------------------
# 3. ITERATIVE — single queue of cross-paired node pairs
# ----------------------------------------------------------------------
def is_symmetric_iterative(root: Optional[TreeNode]) -> bool:
    if root is None:
        return True
    queue: deque = deque([(root.left, root.right)])
    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.right))   # CROSS
        queue.append((a.right, b.left))   # CROSS
    return True


# ----------------------------------------------------------------------
# 4. VIA invert + is_same — slower constant factor, demonstrates fixed-point view
# ----------------------------------------------------------------------
def _invert(node: Optional[TreeNode]) -> Optional[TreeNode]:
    if node is None:
        return None
    return TreeNode(node.val, _invert(node.right), _invert(node.left))


def _is_same(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
    if p is None and q is None:
        return True
    if p is None or q is None:
        return False
    return (
        p.val == q.val
        and _is_same(p.left, q.left)
        and _is_same(p.right, q.right)
    )


def is_symmetric_via_invert(root: Optional[TreeNode]) -> bool:
    return _is_same(root, _invert(root))


# ----------------------------------------------------------------------
# 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 _random_subtree(rng: random.Random, depth: int) -> Optional[TreeNode]:
    if depth == 0 or rng.random() < 0.25:
        return None
    return TreeNode(
        rng.randint(-100, 100),
        _random_subtree(rng, depth - 1),
        _random_subtree(rng, depth - 1),
    )


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


def random_symmetric_tree(rng: random.Random, max_depth: int = 5) -> Optional[TreeNode]:
    """Build a symmetric tree by mirroring a random left subtree to the right."""
    if rng.random() < 0.1:
        return None
    root = TreeNode(rng.randint(-100, 100))
    sub = _random_subtree(rng, max_depth - 1)
    root.left = sub
    root.right = _mirror_subtree(sub)
    return root


def _list_nodes(node: Optional[TreeNode]) -> List[TreeNode]:
    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


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


# ----------------------------------------------------------------------
# 5. STRESS TEST
# ----------------------------------------------------------------------
def stress_test(iterations: int = 500) -> None:
    rng = random.Random(42)

    # Part A: synthesized symmetric trees → must be True under all three impls.
    for _ in range(iterations):
        t = random_symmetric_tree(rng)
        a = is_symmetric_recursive(t)
        b = is_symmetric_iterative(t)
        c = is_symmetric_via_invert(t)
        assert a is True and b is True and c is True, (
            f"synthesized-symmetric flagged asymmetric: rec={a} iter={b} via={c}"
        )

    # Part B: perturb a symmetric tree → expect False (skip if perturbation
    # accidentally remains symmetric — rare for value mutations on non-mirror-pair).
    perturbed = 0
    attempts = 0
    while perturbed < iterations and attempts < iterations * 4:
        attempts += 1
        t = random_symmetric_tree(rng)
        nodes = _list_nodes(t)
        if len(nodes) < 2:
            continue
        c = _clone(t)
        c_nodes = _list_nodes(c)
        idx = rng.randrange(len(c_nodes))
        c_nodes[idx].val = c_nodes[idx].val + 1000  # large delta — unlikely accidental mirror
        a = is_symmetric_recursive(c)
        b = is_symmetric_iterative(c)
        v = is_symmetric_via_invert(c)
        # If still symmetric (perturbed a self-mirroring center node), skip.
        if a or b or v:
            continue
        assert a == b == v == False
        perturbed += 1

    print(
        f"stress_test PASSED — {iterations} symmetric=True + "
        f"{perturbed} perturbed=False (across {attempts} attempts)"
    )


# ----------------------------------------------------------------------
# 6. EDGE CASES
# ----------------------------------------------------------------------
def edge_cases() -> None:
    cases: List[Tuple[List[Optional[int]], bool, str]] = [
        ([], True, "empty"),
        ([1], True, "single"),
        ([1, 2, 2], True, "two children equal"),
        ([1, 2, 3], False, "two children differ"),
        ([1, 2, 2, 3, 4, 4, 3], True, "classic symmetric"),
        ([1, 2, 2, None, 3, None, 3], False, "structurally asymmetric"),
        ([1, 2, 2, 3, 4, 4, 5], False, "value mismatch at depth 3"),
    ]
    for vals, expected, label in cases:
        t = build_tree(vals)
        r = is_symmetric_recursive(t)
        it = is_symmetric_iterative(t)
        v = is_symmetric_via_invert(t)
        ok = r == it == v == expected
        print(
            f"  [{'PASS' if ok else 'FAIL'}] {label}: expected={expected} "
            f"rec={r} iter={it} via={v}"
        )


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