""" LC 102 — Binary Tree Level Order Traversal. Two implementations: 1. level_order_bfs — canonical BFS with deque + level-size snapshot. SHIP THIS. 2. level_order_dfs — DFS with (node, depth) tracking. Alternative; identical output. Plus two follow-up implementations from the same template: right_side_view(root) — LC 199 zigzag_level_order(root) — LC 103 INVARIANT (BFS): at the top of every outer while-iteration, the deque contains exactly the nodes at the current depth, in left-to-right order. CAUTION (build_tree_from_list helper): TreeNode uses __slots__ — never set dynamic attributes on it. Use an external `is_left: bool` toggle (lesson from p16). """ from __future__ import annotations import random import sys from collections import deque from typing import Optional sys.setrecursionlimit(20_000) class TreeNode: __slots__ = ("val", "left", "right") def __init__(self, val: int = 0, left: Optional["TreeNode"] = None, right: Optional["TreeNode"] = None): self.val = val self.left = left self.right = right # ---------------------------------------------------------------------- # Solution A — BFS with level-size snapshot (canonical). # ---------------------------------------------------------------------- def level_order_bfs(root: Optional[TreeNode]) -> list[list[int]]: if root is None: return [] out: list[list[int]] = [] q: deque[TreeNode] = deque([root]) while q: n = len(q) # SNAPSHOT — captures exactly the current level's nodes level: list[int] = [] for _ in range(n): node = q.popleft() level.append(node.val) if node.left is not None: q.append(node.left) if node.right is not None: q.append(node.right) out.append(level) return out # ---------------------------------------------------------------------- # Solution B — DFS with (node, depth) tracking. # ---------------------------------------------------------------------- def level_order_dfs(root: Optional[TreeNode]) -> list[list[int]]: out: list[list[int]] = [] def go(node: Optional[TreeNode], depth: int) -> None: if node is None: return if depth == len(out): out.append([]) out[depth].append(node.val) go(node.left, depth + 1) go(node.right, depth + 1) go(root, 0) return out # ---------------------------------------------------------------------- # LC 199 — Right Side View (BFS, last-of-each-level). # ---------------------------------------------------------------------- def right_side_view(root: Optional[TreeNode]) -> list[int]: if root is None: return [] out: list[int] = [] q: deque[TreeNode] = deque([root]) while q: n = len(q) last_val = 0 for i in range(n): node = q.popleft() if i == n - 1: last_val = node.val if node.left is not None: q.append(node.left) if node.right is not None: q.append(node.right) out.append(last_val) return out # ---------------------------------------------------------------------- # LC 103 — Zigzag Level Order. # ---------------------------------------------------------------------- def zigzag_level_order(root: Optional[TreeNode]) -> list[list[int]]: if root is None: return [] out: list[list[int]] = [] q: deque[TreeNode] = deque([root]) left_to_right = True while q: n = len(q) level: deque[int] = deque() for _ in range(n): node = q.popleft() if left_to_right: level.append(node.val) else: level.appendleft(node.val) if node.left is not None: q.append(node.left) if node.right is not None: q.append(node.right) out.append(list(level)) left_to_right = not left_to_right return out # ---------------------------------------------------------------------- # Helpers. # ---------------------------------------------------------------------- def build_tree_from_list(vals: list[Optional[int]]) -> Optional[TreeNode]: """Level-order list (LC-style with None for missing) → TreeNode. CAUTION: TreeNode uses __slots__. We MUST NOT set attributes on it. External state (`is_left` toggle, parent queue) only. """ if not vals or vals[0] is None: return None root = TreeNode(vals[0]) parents: deque[TreeNode] = deque([root]) i = 1 is_left = True # alternates per child slot parent = parents.popleft() while i < len(vals): v = vals[i] child: Optional[TreeNode] = TreeNode(v) if v is not None else None if is_left: parent.left = child else: parent.right = child if child is not None: parents.append(child) is_left = not is_left if is_left: # We just placed a right child; advance the parent. if not parents: break parent = parents.popleft() i += 1 return root def build_random_binary_tree(rng: random.Random, n: int) -> Optional[TreeNode]: if n == 0: return None root = TreeNode(rng.randint(-1000, 1000)) nodes = [root] for _ in range(n - 1): parent = rng.choice(nodes) val = rng.randint(-1000, 1000) child = TreeNode(val) # pick an available side; if both taken, repick a parent. attempts = 0 while parent.left is not None and parent.right is not None: parent = rng.choice(nodes) attempts += 1 if attempts > 100: return root # tree is full enough if parent.left is None and (parent.right is not None or rng.random() < 0.5): parent.left = child elif parent.right is None: parent.right = child else: parent.left = child nodes.append(child) return root # ---------------------------------------------------------------------- # Stress test. # ---------------------------------------------------------------------- def stress_test() -> None: rng = random.Random(42) n_iter = 1000 for _ in range(n_iter): size = rng.randint(0, 60) root = build_random_binary_tree(rng, size) bfs = level_order_bfs(root) dfs = level_order_dfs(root) assert bfs == dfs, f"BFS vs DFS disagreed:\nBFS={bfs}\nDFS={dfs}" # LC 199 cross-check: right-side view == [level[-1] for level in bfs]. rsv_expected = [lvl[-1] for lvl in bfs] assert right_side_view(root) == rsv_expected, "right_side_view disagrees with last-of-level" # LC 103 cross-check: zigzag == bfs with even/odd levels reversed. zz = zigzag_level_order(root) zz_expected = [ (lvl if i % 2 == 0 else list(reversed(lvl))) for i, lvl in enumerate(bfs) ] assert zz == zz_expected, "zigzag disagrees with manual flip" print(f"stress_test: {n_iter} random binary trees — BFS == DFS; LC 199 and LC 103 cross-check.") # ---------------------------------------------------------------------- # Edge cases. # ---------------------------------------------------------------------- def edge_cases() -> None: # Empty. assert level_order_bfs(None) == [] assert level_order_dfs(None) == [] assert right_side_view(None) == [] assert zigzag_level_order(None) == [] # Single. s = TreeNode(1) assert level_order_bfs(s) == [[1]] assert level_order_dfs(s) == [[1]] assert right_side_view(s) == [1] assert zigzag_level_order(s) == [[1]] # Canonical LC: [3,9,20,null,null,15,7] → [[3],[9,20],[15,7]]. canon = build_tree_from_list([3, 9, 20, None, None, 15, 7]) assert level_order_bfs(canon) == [[3], [9, 20], [15, 7]] assert level_order_dfs(canon) == [[3], [9, 20], [15, 7]] assert right_side_view(canon) == [3, 20, 7] assert zigzag_level_order(canon) == [[3], [20, 9], [15, 7]] # Left-skewed manually. a = TreeNode(1, TreeNode(2, TreeNode(3))) assert level_order_bfs(a) == [[1], [2], [3]] assert level_order_dfs(a) == [[1], [2], [3]] assert right_side_view(a) == [1, 2, 3] # Right-skewed. b = TreeNode(1, None, TreeNode(2, None, TreeNode(3))) assert level_order_bfs(b) == [[1], [2], [3]] assert right_side_view(b) == [1, 2, 3] # Wider canonical zigzag check: [1,2,3,4,null,null,5] → [[1],[3,2],[4,5]]. z = build_tree_from_list([1, 2, 3, 4, None, None, 5]) assert level_order_bfs(z) == [[1], [2, 3], [4, 5]] assert zigzag_level_order(z) == [[1], [3, 2], [4, 5]] print("edge_cases: PASS") if __name__ == "__main__": edge_cases() stress_test() print("ALL TESTS PASSED")