import Mathlib /-! # Binary Tree Level Order Traversal Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level). ## Constraints - The number of nodes in the tree is in the range [0, 2000]. - -1000 <= Node.val <= 1000 ## Provided examples - `root = [3, 9, 20, null, null, 15, 7]` → `[[3], [9, 20], [15, 7]]` - `root = [1]` → `[[1]]` - `root = []` → `[]` ## Synthesized negative examples - invalid input: `root = [1001]` ([structural] a predicate that admits -1000 <= Node.val <= 1000. one above the maximum node value) - invalid input: `root = [1, 2, 3, 4, 1001]` ([structural] a predicate that admits -1000 <= Node.val <= 1000. nested node above maximum; shallow validator accepts) - invalid input: `root = [-1001]` ([structural] a predicate that admits -1000 <= Node.val <= 1000. one below the minimum node value) - `root = [3, 9, 20, null, null, 15, 7]` → `[[3], [20, 9], [7, 15]]` is wrong ([structural] left-to-right order within a level is not required. all levels present; each row is reversed) - `root = [1]` → `[[1, 1]]` is wrong ([structural] level width not required to equal node count. root level lists two entries for one node) - `root = []` → `[[]]` is wrong ([structural] the number of levels is one more than the empty tree has. one empty level instead of zero) -/ namespace PBinaryTreeLevelOrderTraversal abbrev Input := List (Option Int) abbrev Output := List (List Int) /-! ### Specification helpers -/ /-- Bridge: the serialized level-order array already has type `List (Option Int)`, so parsing is the identity. -/ def parseTreeArray (l : List (Option Int)) : List (Option Int) := l /-- The values of the nodes at depth `i` read left to right: the present entries among indices `2^i - 1` through `2^(i+1) - 2`. -/ def levelRow (root : List (Option Int)) (i : Nat) : List Int := (List.range' (2 ^ i - 1) (2 ^ i)).filterMap fun j => (root[j]?).getD none /-- `row` is exactly the level-`i` row of the tree whose compact level-order serialization is `root`. -/ def IsLevelRow (root : List (Option Int)) (i : Nat) (row : List Int) : Prop := row = levelRow root i /-- `n` is the number of nonempty levels of the tree serialized by `root`: the least natural beyond which no depth carries a node. -/ def IsLevelCount (root : List (Option Int)) (n : Nat) : Prop := IsLeast {m | ∀ i, m ≤ i → ∀ row, IsLevelRow root i row → row = []} n /-! ### Validity predicate (V) -/ /-- Valid input: a compact level-order serialization (no node under an absent parent, no trailing nulls) with at most 2000 nodes valued in [-1000, 1000]. -/ def isValidInput (input : Input) : Bool := (List.range input.length).all (fun j => match input[j]? with | some (some _) => j == 0 || (match input[(j - 1) / 2]? with | some (some _) => true | _ => false) | _ => true) && (input.filterMap id).length ≤ 2000 && input.all (fun e => match e with | some v => -1000 ≤ v && v ≤ 1000 | none => true) && input.getLast? ≠ some none /-! ### Ideal specification (P_spec) -/ /-- `result` is the level-order traversal of `input`: it has one row per level of the tree, and each row is exactly that level's values read left to right. -/ def levelOrder_spec (input : Input) (result : Output) : Prop := IsLevelCount input result.length ∧ ∀ i (h : i < result.length), IsLevelRow input i result[i] /-! ### Decidable specification (P_check) -/ /-- Executable form of `IsLevelCount`: every row below `n` is nonempty and every row from `n` to `input.length` is empty. -/ def levelCountCheck (input : Input) (n : Nat) : Bool := (List.range n).all (fun i => !(levelRow input i).isEmpty) && (List.range' n (input.length + 1 - n)).all (fun i => (levelRow input i).isEmpty) /-- Executable checker for `levelOrder_spec`: the level count matches and each row equals that depth's values. -/ def levelOrder_check (input : Input) (result : Output) : Bool := levelCountCheck input result.length && (List.range result.length).all (fun i => result[i]? == some (levelRow input i)) theorem wx_root (input : Input) (result : Output) (hmono : ∀ i j, i ≤ j → levelRow input i = [] → levelRow input j = []) (hbound : ∀ i, input.length ≤ i → levelRow input i = []) : levelOrder_check input result ↔ levelOrder_spec input result := by have hc : levelCountCheck input result.length ↔ IsLevelCount input result.length := by simp only [levelCountCheck, Bool.and_eq_true, List.all_eq_true, List.mem_range, Bool.not_eq_true', List.isEmpty_eq_false_iff, List.mem_range'_1, List.isEmpty_iff, IsLevelCount, IsLevelRow, IsLeast, Set.mem_setOf_eq, mem_lowerBounds] constructor · rintro ⟨ha, hb⟩ refine ⟨?_, ?_⟩ · intro i hi row hr rw [hr] by_cases hbnd : input.length ≤ i · exact hbound i hbnd · exact hb i ⟨hi, by omega⟩ · intro m hm by_contra hn have he := hm m (by omega) (levelRow input m) rfl exact ha m (by omega) he · rintro ⟨ha, hb⟩ constructor · intro i hi he have hni : result.length ≤ i := hb i (by intro j hj row hr rw [hr] exact hmono i j hj he) omega · intro i hi exact ha i hi.1 (levelRow input i) rfl simp only [levelOrder_check, Bool.and_eq_true, hc, levelOrder_spec, List.all_eq_true, List.mem_range, beq_iff_eq, IsLevelRow] apply and_congr Iff.rfl constructor · intro hh i hi exact (List.getElem?_eq_some_iff.mp (hh i hi)).choose_spec · intro hh i hi exact List.getElem?_eq_some_iff.mpr ⟨hi, hh i hi⟩ theorem wx_empty_bound (input : Input) (i : Nat) (hi : input.length ≤ i) : levelRow input i = [] := by simp only [levelRow, List.filterMap_eq_nil_iff, List.mem_range'_1] intro j hj have hp : i < 2 ^ i := Nat.lt_two_pow_self rw [List.getElem?_eq_none (by omega : input.length ≤ j)] rfl theorem wx_root_with_bound (input : Input) (result : Output) (hmono : ∀ i j, i ≤ j → levelRow input i = [] → levelRow input j = []) : levelOrder_check input result ↔ levelOrder_spec input result := by exact wx_root input result hmono (wx_empty_bound input) theorem wx_empty_succ (input : Input) (h : isValidInput input) : ∀ i, levelRow input i = [] → levelRow input (i + 1) = [] := by intro i hi rw [levelRow, List.filterMap_eq_nil_iff] at hi ⊢ intro k hk have hk_bounds := List.mem_range'_1.mp hk have hpow : 0 < 2 ^ i := Nat.two_pow_pos i have hk0 : k ≠ 0 := by simp only [Nat.pow_succ] at hk_bounds omega cases hkget : input[k]? with | none => simp [hkget] | some x => cases x with | none => simp [hkget] | some v => have hklt : k < input.length := (List.getElem?_eq_some_iff.mp hkget).choose have hstruct : (List.range input.length).all (fun j => match input[j]? with | some (some _) => j == 0 || (match input[(j - 1) / 2]? with | some (some _) => true | _ => false) | _ => true) = true := by have hs := h simp only [isValidInput, Bool.and_eq_true] at hs exact hs.1.1.1 have hv := (List.all_eq_true.mp hstruct) k (List.mem_range.mpr hklt) have hp_present : ∃ pv, input[(k - 1) / 2]? = some (some pv) := by cases hp : input[(k - 1) / 2]? with | none => simp [hkget, hk0, hp] at hv | some p => cases p with | none => simp [hkget, hk0, hp] at hv | some pv => exact ⟨pv, rfl⟩ obtain ⟨pv, hp⟩ := hp_present have hparent_mem : (k - 1) / 2 ∈ List.range' (2 ^ i - 1) (2 ^ i) := by apply List.mem_range'_1.mpr simp only [Nat.pow_succ] at hk_bounds constructor <;> omega have hnone := hi ((k - 1) / 2) hparent_mem simp [hp] at hnone theorem wx_empty_mono (input : Input) (h : isValidInput input) : ∀ i j, i ≤ j → levelRow input i = [] → levelRow input j = [] := by intro i j hij hi induction j, hij using Nat.le_induction with | base => exact hi | succ j _ ih => exact wx_empty_succ input h j ih /-- On valid input the checker accepts exactly the specified outputs. -/ theorem levelOrder_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : levelOrder_check input result ↔ levelOrder_spec input result := by exact wx_root_with_bound input result (wx_empty_mono input h) /-! ### Implementation helpers -/ /-- Walks the serialized list, splitting off blocks of size `k + 1` (sizes 1, 2, 4, ... as `k` becomes `2k + 1`) and keeping each block's present values as one level row. -/ def groupLevels : List (Option Int) → Nat → List (List Int) | [], _ => [] | x :: xs, k => ((x :: xs).take (k + 1)).filterMap id :: groupLevels ((x :: xs).drop (k + 1)) (2 * k + 1) termination_by remaining _ => remaining.length decreasing_by · simp only [List.length_drop, List.length_cons] omega /-! ### Main algorithm (impl) -/ /-- Level-order traversal in one linear pass over the serialization: `groupLevels` splits it into blocks of sizes 1, 2, 4, ... and keeps the present values of each block as the next level row. -/ def levelOrderTraversal (input : Input) : Output := groupLevels input 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem levelOrderTraversal_correct (input : Input) (h : isValidInput input) : levelOrder_spec input (levelOrderTraversal input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (parseTreeArray [(some 3), (some 9), (some 20), none, none, (some 15), (some 7)]) #guard isValidInput (parseTreeArray [(some 1)]) #guard isValidInput (parseTreeArray []) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (parseTreeArray [(some 1001)])) #guard !(isValidInput (parseTreeArray [(some 1), (some 2), (some 3), (some 4), (some 1001)])) #guard !(isValidInput (parseTreeArray [(some (-1001))])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard levelOrder_check (parseTreeArray [(some 3), (some 9), (some 20), none, none, (some 15), (some 7)]) [[3], [9, 20], [15, 7]] #guard levelOrder_check (parseTreeArray [(some 1)]) [[1]] #guard levelOrder_check (parseTreeArray []) [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(levelOrder_check (parseTreeArray [(some 3), (some 9), (some 20), none, none, (some 15), (some 7)]) [[3], [20, 9], [7, 15]]) #guard !(levelOrder_check (parseTreeArray [(some 1)]) [[1, 1]]) #guard !(levelOrder_check (parseTreeArray []) [[]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard levelOrderTraversal (parseTreeArray [(some 3), (some 9), (some 20), none, none, (some 15), (some 7)]) == [[3], [9, 20], [15, 7]] #guard levelOrderTraversal (parseTreeArray [(some 1)]) == [[1]] #guard levelOrderTraversal (parseTreeArray []) == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard levelOrder_check (parseTreeArray [(some 3), (some 9), (some 20), none, none, (some 15), (some 7)]) (levelOrderTraversal (parseTreeArray [(some 3), (some 9), (some 20), none, none, (some 15), (some 7)])) #guard levelOrder_check (parseTreeArray [(some 1)]) (levelOrderTraversal (parseTreeArray [(some 1)])) #guard levelOrder_check (parseTreeArray []) (levelOrderTraversal (parseTreeArray [])) end PBinaryTreeLevelOrderTraversal