File: symmetric-tree/solution.py

Date: 2026-06-06

Time: 19:25

Purpose

This file implements LeetCode 101 — Symmetric Tree. It determines whether a binary tree is a mirror image of itself around its center. The file is self-contained: it defines the tree node type, two solution variants (recursive and iterative), a tree builder utility, and a full test suite.

Key Components

TreeNode (lines 9–14)

Standard binary tree node with val, left, right. This is a local definition rather than a shared import — every solution in this repo defines its own TreeNode, which is why hundreds of test files list this module under "Imported By" (they import the class, not the solution logic).

isSymmetric(root) (lines 17–33)

The primary recursive solution. Delegates to a nested is_mirror helper that walks two subtrees simultaneously, comparing mirror-position nodes:

Returns True for an empty tree (null root).

isSymmetricIterative(root) (lines 36–53)

BFS variant using a deque. Seeds the queue with the (root.left, root.right) pair, then pops pairs and enqueues their mirror children. Short-circuits on the first mismatch.

buildtree(vals) (lines 59–75)

Test utility that constructs a TreeNode tree from a level-order list (LeetCode's standard serialization format). None entries represent missing nodes. Used exclusively by the test class.

TestSymmetricTree (lines 78–107)

Seven test cases covering: symmetric tree, asymmetric structure, asymmetric values, single node, empty tree, deep symmetric tree, and left-only child. Every test asserts both the recursive and iterative implementations agree.

Patterns

Dual implementation — Providing both recursive and iterative solutions is a common pattern in this repo's tree problems. The recursive version is cleaner; the iterative version avoids stack overflow on pathological inputs.

Mirror-walk — Instead of serializing the tree and comparing strings, the solution walks two pointers in opposite directions simultaneously. This is O(n) time, O(h) space (recursion depth or queue size).

Inline tests — Tests live in the same file alongside the solution, runnable via python -m unittest or python solution.py. A separate test_solution.py exists alongside this file that likely imports from here.

Dependencies

Imports: deque from collections (used in both the iterative solution and buildtree), Optional from typing, annotations from _future_ (enables forward-reference type hints for TreeNode).

Imported by: The "Imported By" list is enormous (~400 test files) but misleading — those files import the TreeNode class or the tree builder, not the symmetry-check logic. This module effectively serves as a de-facto TreeNode definition for much of the test suite.

Flow

Recursive path: isSymmetric → null-check root → call ismirror(root.left, root.right) → base cases (both null → True, one null → False) → compare values → recurse on outer and inner children. Short-circuits via and: if left.val != right.val, the second ismirror call never happens.

Iterative path: Seed deque with one pair → loop: pop pair → skip if both null → fail if one null or values differ → enqueue two new mirror pairs → return True when queue empties.

Invariants

Error Handling

There is none beyond structural null checks, which is appropriate — the contract is that inputs are valid TreeNode trees or None. No exceptions are raised or caught. Invalid inputs (e.g., non-list to buildtree) would raise standard Python errors.

Topics to Explore

Beliefs