Date: 2026-06-06
Time: 15:26
This file implements LeetCode 144 — Binary Tree Preorder Traversal. It owns the TreeNode definition, the iterative traversal algorithm, and its own unit tests — a self-contained solution module following the repo's per-problem directory convention.
TreeNode (lines 7–10)Standard binary tree node with val, left, right. This is the canonical definition used across the repo — the massive "Imported By" list shows that hundreds of test files reference this module (likely importing TreeNode for test setup).
Solution.preorderTraversal (lines 14–28)Returns node values in preorder (root → left → right) using an explicit stack rather than recursion.
Contract: accepts Optional[TreeNode], returns List[int]. Returns [] for a null root.
Iterative DFS with a stack. The key trick is push order: right child is pushed *before* left child (lines 25–28). Since stacks are LIFO, this guarantees left is popped (and thus visited) first — producing root-left-right order without recursion.
This avoids Python's default recursion limit (~1000), making it safe for deep/skewed trees up to memory limits.
Self-contained solution module. Tests live in the same file (below the # --- Tests --- marker) and also in a separate testsolution.py. The file doubles as both importable module and standalone test runner via if name == "main_".
Imports: typing.List, typing.Optional, unittest — all stdlib, no external deps.
Imported by: The TreeNode class from this file is imported by 400+ test files across the repo. This makes it a de facto shared definition — any change to TreeNode's constructor signature would be a breaking change across most of the codebase.
1. Guard clause: null root → return []
2. Initialize result = [], seed stack = [root]
3. Loop: pop node, append its value to result
4. Push right child (if exists), then left child (if exists)
5. Stack drains naturally when all nodes are visited → return result
The data transformation is: TreeNode graph → flat List[int] via depth-first, preorder walk.
None.None explicit — the function assumes a well-formed tree (no cycles, no non-TreeNode objects). An infinite cycle in the tree would cause an infinite loop. There's no input validation beyond the null-root guard; this is standard for LeetCode solutions where inputs are guaranteed valid.
binary-tree-inorder-traversal/solution.py — Compare the iterative stack technique for inorder (requires tracking "go left" vs "process" states, making it more complex)binary-tree-paths/solution.py — Uses the same tree structure but must track full root-to-leaf paths, showing how traversal adapts to different output shapesconstruct-string-from-binary-tree/solution.py:Solution.tree2str — Another preorder walk, but with parenthesization rules that complicate the right-child-omission logiciterative-vs-recursive-tree-traversal — Why this repo consistently uses iterative approaches (stack safety, interview preference) vs the 3-line recursive versionpreorder-iterative-push-order — Right child is pushed before left child to ensure left subtree is visited first in the LIFO stacktreenode-shared-definition — TreeNode from this file is imported by 400+ test files, making it the repo's de facto shared binary tree node classpreorder-null-root-returns-empty — preorderTraversal(None) returns [], not None or an errorpreorder-linear-time-space — The algorithm visits each node exactly once (O(n) time) and uses O(n) stack space in the worst case (skewed tree)