Date: 2026-06-06
Time: 17:20
leaf-similar-trees/solution.pyThis file solves LeetCode 872 - Leaf-Similar Trees. It determines whether two binary trees have the same leaf value sequence — the left-to-right ordering of values at leaf nodes. The file is self-contained: it defines the tree data structure, the solution, a tree builder utility, and unit tests.
TreeNode (line 9-12) — Standard binary tree node with val, left, right. This is the canonical LeetCode tree node definition, used across many solutions in this repo.
Solution.leafSimilar (line 16-29) — The core algorithm. Takes two tree roots, extracts the leaf sequence from each, and compares them for equality.
get_leaves (line 25-29) — Nested helper that recursively collects leaf values via DFS. The base cases are:
None node → empty listThis guarantees left-to-right ordering because left subtree is always visited before right.
build_tree (line 32-46) — Constructs a TreeNode tree from a level-order list (LeetCode's standard serialization format where None represents absent nodes). Uses BFS with a queue to assign children.
TestLeafSimilar (line 49-75) — Six test cases covering: the two LeetCode examples, single-node trees (equal and unequal), trees with different structures but identical leaf sequences, and mismatched leaf counts.
get_leaves uses the classic "collect and concatenate" pattern for tree traversal. It builds the result bottom-up by concatenating left and right subtree results.solution.py bundles the solution class, any necessary data structures, helper utilities, and tests in one file.leafSimilar uses camelCase (matching LeetCode's interface), while helper functions use snake_case (Python convention).Imports: annotations (for forward-reference type hints in TreeNode), unittest, typing.Optional.
Imported by: The "Imported By" list is misleadingly large — it reflects testsolution.py files across the repo that likely import a shared test runner or tree utility, not this specific file. The actual leaf-similar-trees/testsolution.py imports from this module.
1. Caller passes two tree roots to leafSimilar.
2. get_leaves performs a depth-first traversal of each tree, collecting values only at leaf nodes (nodes with no children).
3. The two resulting lists are compared with ==.
For a tree like [3, 5, 1, 6, 2, 9, 8, None, None, 7, 4], get_leaves produces [6, 7, 4, 9, 8] — the leaves read left-to-right.
None input produces an empty leaf list: a None root returns [], so two None trees are considered leaf-similar (both empty).build_tree assumes valid level-order input: it doesn't guard against malformed input (e.g., children specified for a None node).None. The code trusts its inputs — no validation on tree structure, no exception handling. This is standard for LeetCode solutions where inputs are guaranteed well-formed.
get_leaves builds intermediate lists via concatenation (+), which is O(n) per concatenation. For a balanced tree of n nodes this gives O(n log n) total work. A production version would use a single list with .append() or a generator to achieve O(n). For LeetCode's constraints (up to 200 nodes), this doesn't matter.
leaf-sequence-is-left-to-right — get_leaves always returns leaves in left-to-right order because it recurses into node.left before node.right and concatenates in that ordernone-roots-are-leaf-similar — Two None roots are considered leaf-similar because get_leaves(None) returns [] and [] == [] is Truelist-concat-not-optimal — The get_leaves implementation uses list concatenation (+) giving O(n log n) for balanced trees instead of the optimal O(n) with append or generatorsbuild-tree-uses-bfs — build_tree constructs trees via BFS queue traversal of the level-order array, matching LeetCode's standard serialization format