import Mathlib /-! # Same Tree Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value. ## Constraints - The number of nodes in both trees is in the range [0, 100]. - -10^4 <= Node.val <= 10^4 ## Provided examples - `p = [1, 2, 3], q = [1, 2, 3]` → `true` - `p = [1, 2], q = [1, null, 2]` → `false` - `p = [1, 2, 1], q = [1, 1, 2]` → `false` ## Synthesized negative examples - invalid input: `p = [10001], q = []` ([structural] a predicate that admits -10^4 <= Node.val <= 10^4. one past the stated maximum) - invalid input: `p = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], q = []` ([structural] a predicate that admits The number of nodes in both trees is in the range [0, 100].. 101 nodes in p exceeds the stated range) - invalid input: `p = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], q = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]` ([structural] a predicate that admits The number of nodes in both trees is in the range [0, 100].. 101 total nodes though each tree is within 100; per-tree check accepts) - `p = [1, 2, 3], q = [1, 2, 3]` → `false` is wrong ([structural] only the empty-tree case is checked, non-empty nodes are never compared. identical non-empty trees are rejected) - `p = [1, 2], q = [1, null, 2]` → `true` is wrong ([structural] structural identity is dropped, so only node values matter. Both trees have values [1,2], so values-only check passes.) - `p = [1, 2, 1], q = [1, 1, 2]` → `true` is wrong ([structural] node values are not required to match. structurally identical, only values at children differ) -/ namespace PSameTree /-! ### Representation -/ /-- A serialized tree position is either absent or holds an integer node value. -/ inductive NodeSlot where | none | val (n : Int) instance instOfNatNodeSlot (n : Nat) : OfNat NodeSlot n where ofNat := .val (Int.ofNat n) instance instNegNodeSlot : Neg NodeSlot where neg slot := match slot with | .none => .none | .val n => .val (-n) /-- The frozen serialized form may write a node with `some`; it denotes `NodeSlot.val`. -/ def some (n : Int) : NodeSlot := .val n abbrev Input := (List NodeSlot) × (List NodeSlot) abbrev Output := Bool /-! ### Specification helpers -/ /-- Turns a tree at one frontier position into its serialized slot. -/ def slotOfTree : Tree Int → NodeSlot | .nil => .none | .node value _ _ => .val value /-- Returns the two child positions of a tree, with no positions below an absent tree. -/ def childTrees : Tree Int → List (Tree Int) | .nil => [] | .node _ left right => [left, right] /-- Returns the tree positions occurring at a given breadth-first depth. -/ def treeFrontier (tree : Tree Int) : Nat → List (Tree Int) | 0 => match tree with | .nil => [] | .node _ _ _ => [tree] | depth + 1 => (treeFrontier tree depth).flatMap childTrees /-- Returns the number of breadth-first levels in a tree. -/ def treeHeight : Tree Int → Nat | .nil => 0 | .node _ left right => max (treeHeight left) (treeHeight right) + 1 /-- Removes leading absent slots from a list. -/ def dropLeadingNone : List NodeSlot → List NodeSlot | .none :: slots => dropLeadingNone slots | slots => slots /-- Removes trailing absent slots from a list. -/ def trimTrailingNone (slots : List NodeSlot) : List NodeSlot := (dropLeadingNone slots.reverse).reverse /-- Produces the canonical LeetCode level-order serialization of a binary tree. -/ def levelOrder (tree : Tree Int) : List NodeSlot := trimTrailingNone ((List.range (treeHeight tree)).flatMap (fun depth => (treeFrontier tree depth).map slotOfTree)) /-- Counts the entries that contain a node value. -/ def nodeValueCount : List NodeSlot → Nat | [] => 0 | .none :: slots => nodeValueCount slots | .val _ :: slots => nodeValueCount slots + 1 /-- Tests whether a slot is absent or contains a value in the stated range. -/ def nodeValueInRange : NodeSlot → Bool | .none => true | .val n => -10000 ≤ n && n ≤ 10000 /-- Checks breadth-first levels using the number of available child positions and a fuel bound. -/ def validLevelOrderAux : Nat → List NodeSlot → Nat → Bool | 0, _, _ => false | fuel + 1, slots, width => let level := slots.take width let rest := slots.drop width let values := nodeValueCount level if values == 0 then level.length == 0 else if level.length < width then true else validLevelOrderAux fuel rest (2 * values) /-- Recognizes a canonical LeetCode level-order serialization. -/ def isLevelOrder (slots : List NodeSlot) : Bool := validLevelOrderAux (slots.length + 1) slots 1 && (trimTrailingNone slots).length == slots.length /-- Two serializations encode binary trees with equal structure and equal node values. -/ def IsSameTree (p q : List NodeSlot) : Prop := ∃ leftTree rightTree : Tree Int, levelOrder leftTree = p ∧ levelOrder rightTree = q ∧ leftTree = rightTree /-! ### Validity predicate (V) -/ /-- The frozen serialized form may write an absent node with `null`; it denotes `NodeSlot.none`. -/ def null : NodeSlot := .none /-- Valid input: canonical serializations with at most 100 nodes each and overall, and values in range. -/ def isValidInput (input : Input) : Bool := let p := input.1 let q := input.2 isLevelOrder p && isLevelOrder q && nodeValueCount p ≤ 100 && nodeValueCount q ≤ 100 && nodeValueCount p + nodeValueCount q ≤ 100 && p.all nodeValueInRange && q.all nodeValueInRange /-! ### Ideal specification (P_spec) -/ /-- The result is true exactly when the two serialized inputs encode the same binary tree. -/ def sameTree_spec (input : Input) (result : Output) : Prop := result ↔ IsSameTree input.1 input.2 /-! ### Decidable specification (P_check) -/ /-- The frozen serialized form may write an absent node with `none`; it denotes `NodeSlot.none`. -/ def none : NodeSlot := .none /-- Decidable equality of slots by constructor and stored value. -/ instance instDecidableEqNodeSlot : DecidableEq NodeSlot | .none, .none => isTrue rfl | .none, .val _ => isFalse (fun h => NodeSlot.noConfusion h) | .val _, .none => isFalse (fun h => NodeSlot.noConfusion h) | .val m, .val n => if h : m = n then isTrue (congrArg NodeSlot.val h) else isFalse (fun heq => h (NodeSlot.val.inj heq)) /-- Executable checker for `sameTree_spec`: on valid canonical serializations the encoded trees are equal exactly when the lists are equal. -/ def sameTree_check (input : Input) (result : Output) : Bool := decide (result ↔ input.1 = input.2) /-- Serialize a forest level by level for `n` levels. -/ def fLevels : Nat → List (Tree Int) → List NodeSlot | 0, _ => [] | n + 1, ts => ts.map slotOfTree ++ fLevels n (ts.flatMap childTrees) /-- Rebuild one level of trees from its slots and the list of child trees. -/ def assembleLevel : List NodeSlot → List (Tree Int) → List (Tree Int) | [], _ => [] | .none :: l, cs => .nil :: assembleLevel l cs | .val v :: l, c1 :: c2 :: cs => .node v c1 c2 :: assembleLevel l cs | .val v :: l, _ => .node v .nil .nil :: assembleLevel l [] theorem fLevels_nil (n : Nat) : fLevels n [] = [] := by induction n with | zero => rfl | succ n ih => simp [fLevels, ih] theorem fLevels_nils (n j : Nat) : ∃ k, fLevels n (List.replicate j .nil) = List.replicate k .none := by cases n with | zero => exact ⟨0, rfl⟩ | succ n => refine ⟨j, ?_⟩ have h1 : (List.replicate j (Tree.nil : Tree Int)).flatMap childTrees = [] := by simp [List.flatMap_eq_nil_iff, childTrees] simp only [fLevels, h1, fLevels_nil, List.map_replicate, List.append_nil] rfl theorem dl_append (u v : List NodeSlot) : dropLeadingNone (u ++ v) = if dropLeadingNone u = [] then dropLeadingNone v else dropLeadingNone u ++ v := by induction u with | nil => rfl | cons a u ih => cases a with | none => exact ih | val x => simp [dropLeadingNone] theorem dl_replicate (k : Nat) : dropLeadingNone (List.replicate k .none) = [] := by induction k with | zero => rfl | succ k ih => exact ih theorem dl_suffix (x : List NodeSlot) : dropLeadingNone x <:+ x := by induction x with | nil => exact List.suffix_refl _ | cons a x ih => cases a with | none => exact ih.trans (List.suffix_cons _ _) | val v => exact List.suffix_refl _ theorem trim_append_congr (a b b' : List NodeSlot) (h : trimTrailingNone b = trimTrailingNone b') : trimTrailingNone (a ++ b) = trimTrailingNone (a ++ b') := by unfold trimTrailingNone at * have h' := List.reverse_injective h simp only [List.reverse_append, dl_append, h'] theorem trim_replicate (k : Nat) : trimTrailingNone (List.replicate k .none) = [] := by simp [trimTrailingNone, dl_replicate] theorem trim_append_nones (s : List NodeSlot) (k : Nat) : trimTrailingNone (s ++ List.replicate k .none) = trimTrailingNone s := by have := trim_append_congr s (List.replicate k .none) [] (by rw [trim_replicate]; rfl) simpa using this theorem trim_self (s : List NodeSlot) (h : (trimTrailingNone s).length = s.length) : trimTrailingNone s = s := by unfold trimTrailingNone at * have h2 : dropLeadingNone s.reverse = s.reverse := (dl_suffix s.reverse).eq_of_length (by simpa using h) simp [h2] theorem fLevels_stable : ∀ (n : Nat) (ts : List (Tree Int)), (∀ t ∈ ts, treeHeight t ≤ n) → ∀ m, n ≤ m → trimTrailingNone (fLevels m ts) = trimTrailingNone (fLevels n ts) := by intro n induction n with | zero => intro ts hts m _ have hnil : ∀ t ∈ ts, t = .nil := by intro t ht have := hts t ht cases t with | nil => rfl | node v l r => simp [treeHeight] at this cases m with | zero => rfl | succ m => have h1 : ts.flatMap childTrees = [] := by rw [List.flatMap_eq_nil_iff] intro t ht rw [hnil t ht] rfl have h2 : ts.map slotOfTree = List.replicate ts.length .none := by rw [List.eq_replicate_iff] refine ⟨by simp, ?_⟩ intro x hx obtain ⟨t, ht, rfl⟩ := List.mem_map.mp hx rw [hnil t ht] rfl simp only [fLevels, h1, fLevels_nil, h2, List.append_nil, trim_replicate] rfl | succ n ih => intro ts hts m hm obtain ⟨m, rfl⟩ : ∃ m', m = m' + 1 := ⟨m - 1, by omega⟩ simp only [fLevels] apply trim_append_congr apply ih · intro c hc obtain ⟨t, ht, hct⟩ := List.mem_flatMap.mp hc have := hts t ht cases t with | nil => simp [childTrees] at hct | node v l r => simp only [childTrees, List.mem_cons, List.not_mem_nil, or_false] at hct simp only [treeHeight] at this rcases hct with rfl | rfl <;> omega · omega theorem flatMap_frontier : ∀ (N : Nat) (fr : Nat → List (Tree Int)), (∀ d, fr (d + 1) = (fr d).flatMap childTrees) → (List.range N).flatMap (fun d => (fr d).map slotOfTree) = fLevels N (fr 0) := by intro N induction N with | zero => intro fr _; rfl | succ N ih => intro fr hfr rw [List.range_succ_eq_map, List.flatMap_cons, List.flatMap_map, ih (fun d => fr (d + 1)) (fun d => hfr (d + 1)), hfr 0] rfl theorem levelOrder_eq (t : Tree Int) (N : Nat) (hN : treeHeight t ≤ N) : levelOrder t = trimTrailingNone (fLevels N [t]) := by cases t with | nil => cases N with | zero => rfl | succ N => simp only [fLevels, fLevels_nil, List.map_cons, List.map_nil, List.flatMap_cons, List.flatMap_nil, childTrees, List.append_nil] rfl | node v l r => unfold levelOrder rw [flatMap_frontier _ (treeFrontier (.node v l r)) (fun d => rfl)] exact (fLevels_stable _ [.node v l r] (by simp) N hN).symm theorem assemble_spec : ∀ (l : List NodeSlot) (cs : List (Tree Int)), cs.length = 2 * nodeValueCount l → (assembleLevel l cs).map slotOfTree = l ∧ (assembleLevel l cs).flatMap childTrees = cs ∧ (assembleLevel l cs).length = l.length ∧ ∀ m, (∀ c ∈ cs, treeHeight c ≤ m) → ∀ t ∈ assembleLevel l cs, treeHeight t ≤ m + 1 := by intro l induction l with | nil => intro cs hcs simp only [nodeValueCount] at hcs have : cs = [] := List.eq_nil_of_length_eq_zero hcs subst this simp [assembleLevel] | cons a l ih => intro cs hcs cases a with | none => simp only [nodeValueCount] at hcs obtain ⟨h1, h2, h3, h4⟩ := ih cs hcs refine ⟨by simp [assembleLevel, h1, slotOfTree], by simp [assembleLevel, h2, childTrees], by simp [assembleLevel, h3], ?_⟩ intro m hm t ht simp only [assembleLevel, List.mem_cons] at ht rcases ht with rfl | ht · simp [treeHeight] · exact h4 m hm t ht | val v => simp only [nodeValueCount] at hcs rcases cs with _ | ⟨c1, _ | ⟨c2, cs⟩⟩ · simp at hcs · simp at hcs; omega · simp only [List.length_cons] at hcs obtain ⟨h1, h2, h3, h4⟩ := ih cs (by omega) refine ⟨by simp [assembleLevel, h1, slotOfTree], by simp [assembleLevel, h2, childTrees], by simp [assembleLevel, h3], ?_⟩ intro m hm t ht simp only [assembleLevel, List.mem_cons] at ht rcases ht with rfl | ht · have e1 := hm c1 (by simp) have e2 := hm c2 (by simp) simp only [treeHeight] omega · exact h4 m (fun c hc => hm c (by simp [hc])) t ht theorem aux_succ (n : Nat) (s : List NodeSlot) (w : Nat) : validLevelOrderAux (n + 1) s w = if (nodeValueCount (s.take w) == 0) = true then ((s.take w).length == 0) else if (s.take w).length < w then true else validLevelOrderAux n (s.drop w) (2 * nodeValueCount (s.take w)) := rfl theorem decode : ∀ (fuel : Nat) (s : List NodeSlot) (w : Nat), 1 ≤ w → validLevelOrderAux fuel s w = true → ∃ ts : List (Tree Int), ts.length = w ∧ (∀ t ∈ ts, treeHeight t ≤ fuel) ∧ ∃ k, fLevels fuel ts = s ++ List.replicate k .none := by intro fuel induction fuel with | zero => intro s w _ h; simp [validLevelOrderAux] at h | succ n ih => intro s w hw h rw [aux_succ] at h by_cases h0 : nodeValueCount (s.take w) = 0 · rw [if_pos (beq_iff_eq.mpr h0)] at h have hs : s = [] := by have := beq_iff_eq.mp h simp only [List.length_take] at this exact List.eq_nil_of_length_eq_zero (by omega) subst hs obtain ⟨k, hk⟩ := fLevels_nils n (2 * 0) refine ⟨List.replicate w .nil, by simp, by simp [treeHeight], w, ?_⟩ have h1 : (List.replicate w (Tree.nil : Tree Int)).flatMap childTrees = [] := by simp [List.flatMap_eq_nil_iff, childTrees] simp only [fLevels, h1, fLevels_nil, List.map_replicate, List.append_nil, List.nil_append] rfl · rw [if_neg (by simpa using h0)] at h by_cases hlt : (s.take w).length < w · have hsl : s.length < w := by simp only [List.length_take] at hlt; omega have htake : s.take w = s := List.take_of_length_le (by omega) rw [htake] at h0 obtain ⟨h1, h2, h3, h4⟩ := assemble_spec s (List.replicate (2 * nodeValueCount s) .nil) (by simp) obtain ⟨k, hk⟩ := fLevels_nils n (2 * nodeValueCount s) refine ⟨assembleLevel s (List.replicate (2 * nodeValueCount s) .nil) ++ List.replicate (w - s.length) .nil, by simp [h3]; omega, ?_, w - s.length + k, ?_⟩ · intro t ht rcases List.mem_append.mp ht with ht | ht · have := h4 0 (by simp [treeHeight]) t ht omega · simp only [List.mem_replicate] at ht rw [ht.2] simp [treeHeight] · have h5 : (List.replicate (w - s.length) (Tree.nil : Tree Int)).flatMap childTrees = [] := by simp [List.flatMap_eq_nil_iff, childTrees] simp only [fLevels, List.map_append, h1, List.flatMap_append, h2, h5, List.append_nil, hk, List.map_replicate, List.replicate_add, List.append_assoc] rfl · rw [if_neg hlt] at h have hlen : (s.take w).length = w := by simp only [List.length_take] at hlt ⊢; omega obtain ⟨cs, hcl, hch, k, hk⟩ := ih (s.drop w) _ (by omega) h obtain ⟨h1, h2, h3, h4⟩ := assemble_spec (s.take w) cs hcl refine ⟨assembleLevel (s.take w) cs, by rw [h3, hlen], h4 n hch, k, ?_⟩ simp only [fLevels, h1, h2, hk, ← List.append_assoc, List.take_append_drop] theorem exists_tree (s : List NodeSlot) (h : isLevelOrder s = true) : ∃ t : Tree Int, levelOrder t = s := by unfold isLevelOrder at h simp only [Bool.and_eq_true, beq_iff_eq] at h obtain ⟨hv, hl⟩ := h obtain ⟨ts, hlen, hh, k, hF⟩ := decode (s.length + 1) s 1 le_rfl hv obtain ⟨t, rfl⟩ := List.length_eq_one_iff.mp hlen refine ⟨t, ?_⟩ rw [levelOrder_eq t (s.length + 1) (hh t (by simp)), hF, trim_append_nones, trim_self s hl] theorem sameTree_bridge (p q : List NodeSlot) (hp : isLevelOrder p = true) : IsSameTree p q ↔ p = q := by constructor · rintro ⟨a, b, ha, hb, rfl⟩ exact ha.symm.trans hb · rintro rfl obtain ⟨t, ht⟩ := exists_tree p hp exact ⟨t, t, ht, ht, rfl⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem sameTree_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : sameTree_check input result ↔ sameTree_spec input result := by have hp : isLevelOrder input.1 = true := by unfold isValidInput at h simp only [Bool.and_eq_true] at h exact h.1.1.1.1.1.1 unfold sameTree_check sameTree_spec rw [decide_eq_true_iff] exact iff_congr Iff.rfl (sameTree_bridge input.1 input.2 hp).symm /-! ### Main algorithm (impl) -/ /-- Decides tree equality as the checker's boolean at result `true`, i.e. linear list equality of the two canonical level-order serializations. -/ def isSameTree (input : Input) : Output := sameTree_check input true /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem isSameTree_correct (input : Input) (h : isValidInput input) : sameTree_spec input (isSameTree input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([1, 2, 3], [1, 2, 3]) #guard isValidInput ([1, 2], [1, null, 2]) #guard isValidInput ([1, 2, 1], [1, 1, 2]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([10001], [])) #guard !(isValidInput ([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [])) #guard !(isValidInput ([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard sameTree_check ([1, 2, 3], [1, 2, 3]) true #guard sameTree_check ([1, 2], [(some 1), none, (some 2)]) false #guard sameTree_check ([1, 2, 1], [1, 1, 2]) false /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(sameTree_check ([1, 2, 3], [1, 2, 3]) false) #guard !(sameTree_check ([1, 2], [(some 1), none, (some 2)]) true) #guard !(sameTree_check ([1, 2, 1], [1, 1, 2]) true) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard isSameTree ([1, 2, 3], [1, 2, 3]) == true #guard isSameTree ([1, 2], [(some 1), none, (some 2)]) == false #guard isSameTree ([1, 2, 1], [1, 1, 2]) == false /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard sameTree_check ([1, 2, 3], [1, 2, 3]) (isSameTree ([1, 2, 3], [1, 2, 3])) #guard sameTree_check ([1, 2], [(some 1), none, (some 2)]) (isSameTree ([1, 2], [(some 1), none, (some 2)])) #guard sameTree_check ([1, 2, 1], [1, 1, 2]) (isSameTree ([1, 2, 1], [1, 1, 2])) end PSameTree