import Mathlib /-! # Closest Leaf In A Binary Tree Given the root of a binary tree where every node has a unique value and a target integer k, return the value of the nearest leaf node to the target k in the tree. Nearest to a leaf means the least number of edges traveled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children. ## Constraints - The number of nodes in the tree is in the range [1, 1000]. - 1 <= Node.val <= 1000 - All the values of the tree are unique. - There exist some node in the tree where Node.val == k. ## Provided examples - `root = [1, 3, 2], k = 1` → `2` - `root = [1], k = 1` → `1` - `root = [1, 2, 3, 4, null, null, null, 5, null, 6], k = 2` → `3` ## Synthesized negative examples - invalid input: `root = [0, 1, 2], k = 1` ([structural] a predicate that admits 1 <= Node.val <= 1000. node value 0 below the stated minimum; checking only that k exists accepts) - invalid input: `root = [1, 1, 2], k = 2` ([structural] a predicate that admits All the values of the tree are unique.. duplicate value 1 at root and left child; predicate checking only k existence accepts) - invalid input: `root = [1, 2, 3], k = 4` ([structural] a predicate that admits There exist some node in the tree where Node.val == k.. k=4 absent from tree; a predicate assuming k exists accepts) - `root = [1, 3, 2], k = 1` → `1` is wrong ([structural] nearest node is not required to be a leaf; the target itself is accepted. target value 1 is distance 0 but is not a leaf) - `root = [1], k = 1` → `0` is wrong ([structural] returned the distance to the leaf instead of the leaf value. 0 is the correct distance but not the value of the only leaf) - `root = [1, 2, 3, 4, null, null, null, 5, null, 6], k = 2` → `6` is wrong ([structural] nearest condition omitted; any leaf accepted. 6 is a leaf but farthest from k) -/ namespace PClosestLeafInABinaryTree abbrev Input := (List (Option Nat)) × (Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- Binary tree with natural-number values, the decode target for a level-order serialization. -/ inductive BinTree where | nil : BinTree | node (value : Nat) (left right : BinTree) /-- Take the children of the non-null entries of `vals` from the front of `rest`, returning the child entries and the leftover. -/ def takeChildren : List (Option Nat) → List (Option Nat) → List (Option Nat) × List (Option Nat) | [], rest => ([], rest) | none :: vals, rest => takeChildren vals rest | some _ :: vals, rest => let (c, rest') := takeChildren vals (rest.drop 2) (rest.take 2 ++ c, rest') /-- Assemble one level of subtrees from node values `vals` and the already-built child subtrees `ts`. -/ def attach : List (Option Nat) → List (Option BinTree) → List (Option BinTree) | [], _ => [] | none :: vals, ts => none :: attach vals ts | some v :: vals, ts => (BinTree.node v (((ts[0]?).bind id).getD BinTree.nil) (((ts[1]?).bind id).getD BinTree.nil)) :: attach vals (ts.drop 2) /-- Build the subtrees rooted at one level of the serialization, reading deeper levels from `rest`; `fuel` bounds the recursion. -/ def buildLevel : Nat → List (Option Nat) → List (Option Nat) → List (Option BinTree) × List (Option Nat) | 0, vals, rest => (vals.map fun _ => none, rest) | fuel + 1, vals, rest => if vals.all Option.isNone then (vals.map fun _ => none, rest) else let (c, rest') := takeChildren vals rest let (ts, rest'') := buildLevel fuel c rest' (attach vals ts, rest'') /-- Decode a level-order serialization with `none` as null into a tree, giving `BinTree.nil` when the serialization is malformed. -/ def decode (l : List (Option Nat)) : BinTree := match l with | [] => BinTree.nil | v :: rest => match buildLevel l.length [v] rest with | ([some t], []) => t | (_, _) => BinTree.nil /-- `v` is the value of a leaf of the tree: a node whose two children are empty. -/ def isLeafInTree : BinTree → Nat → Prop | BinTree.nil, _ => False | BinTree.node x l r, v => x = v ∧ l = BinTree.nil ∧ r = BinTree.nil ∨ isLeafInTree l v ∨ isLeafInTree r v /-- The tree decoded from `l` has a leaf node with value `v`. -/ def IsLeafNode (l : List (Option Nat)) (v : Nat) : Prop := isLeafInTree (decode l) v /-- The sequence of left (`false`) and right (`true`) steps from the root to the node valued `v`, if that node exists. -/ def pathTo : BinTree → Nat → Option (List Bool) | BinTree.nil, _ => none | BinTree.node x l r, v => if x = v then some [] else match pathTo l v, pathTo r v with | some p, _ => some (false :: p) | none, some p => some (true :: p) | none, none => none /-- Drop the longest common prefix of two step sequences and return the two remainders. -/ def dropCommonPrefix : List Bool → List Bool → List Bool × List Bool | a :: as, b :: bs => if a = b then dropCommonPrefix as bs else (a :: as, b :: bs) | as, bs => (as, bs) /-- `d` is the number of edges on the path between the nodes valued `a` and `b` in the tree decoded from `l`. -/ def TreeDistance (l : List (Option Nat)) (a b d : Nat) : Prop := ∃ pa pb : List Bool, pathTo (decode l) a = some pa ∧ pathTo (decode l) b = some pb ∧ (dropCommonPrefix pa pb).1.length + (dropCommonPrefix pa pb).2.length = d /-! ### Validity predicate (V) -/ /-- Valid input: a well-formed serialization of a tree with 1 to 1000 nodes whose values are unique and in 1 to 1000, with a node valued `k`. -/ def isValidInput (input : Input) : Bool := let root := input.1 let vals := root.filterMap id (match decode root with | BinTree.nil => false | _ => true) && decide (1 ≤ vals.length) && decide (vals.length ≤ 1000) && vals.all (fun v => decide (1 ≤ v) && decide (v ≤ 1000)) && vals.all (fun v => decide ((vals.filter (fun w => w == v)).length = 1)) && vals.contains input.2 /-! ### Ideal specification (P_spec) -/ /-- `result` is the value of a leaf of the decoded tree, and no leaf is closer to the node valued `k` than that leaf is. -/ def closestLeafValue_spec (input : Input) (result : Output) : Prop := IsLeafNode input.1 result ∧ ∀ ℓ : Nat, IsLeafNode input.1 ℓ → ∀ dres dℓ : Nat, TreeDistance input.1 input.2 result dres → TreeDistance input.1 input.2 ℓ dℓ → dres ≤ dℓ /-! ### Decidable specification (P_check) -/ /-- The empty-tree test on a decoded tree. -/ def isEmptyTree : BinTree → Bool | BinTree.nil => true | BinTree.node _ _ _ => false /-- Decidable form of `isLeafInTree`: `v` is the value of a node whose two children are empty. -/ def isLeafValInTree : BinTree → Nat → Bool | BinTree.nil, _ => false | BinTree.node x l r, v => (x == v && isEmptyTree l && isEmptyTree r) || isLeafValInTree l v || isLeafValInTree r v /-- Decidable form of `IsLeafNode`: the tree decoded from `l` has a leaf valued `v`. -/ def isLeafVal (l : List (Option Nat)) (v : Nat) : Bool := isLeafValInTree (decode l) v /-- The values of the leaves of a tree, gathered by the same traversal that tests leaf membership. -/ def leafValuesOf : BinTree → List Nat | BinTree.nil => [] | BinTree.node x BinTree.nil BinTree.nil => [x] | BinTree.node _ l r => leafValuesOf l ++ leafValuesOf r /-- The number of edges on the unique path between the nodes valued `a` and `b` in the tree decoded from `l`, or 0 when either value is absent. -/ def treeDist (l : List (Option Nat)) (a b : Nat) : Nat := match pathTo (decode l) a, pathTo (decode l) b with | some pa, some pb => (dropCommonPrefix pa pb).1.length + (dropCommonPrefix pa pb).2.length | _, _ => 0 /-- Executable checker for `closestLeafValue_spec` over the decoded tree's leaves. -/ def closestLeafValue_check (input : Input) (result : Output) : Bool := isLeafVal input.1 result && (leafValuesOf (decode input.1)).all (fun ℓ => decide (treeDist input.1 input.2 result ≤ treeDist input.1 input.2 ℓ)) theorem root_of_bridges (B : ∀ t v, isLeafValInTree t v = true ↔ isLeafInTree t v) (M : ∀ t v, v ∈ leafValuesOf t ↔ isLeafInTree t v) (P : ∀ t v, isLeafInTree t v → ∃ p, pathTo t v = some p) (input : Input) (result : Output) : closestLeafValue_check input result ↔ closestLeafValue_spec input result := by simp only [closestLeafValue_check, Bool.and_eq_true, isLeafVal, B, List.all_eq_true, decide_eq_true_eq, M, closestLeafValue_spec, IsLeafNode] constructor · rintro ⟨hr, hc⟩ refine ⟨hr, ?_⟩ intro l hl dr dl hdr hdl obtain ⟨pa, pb, ha, hb, hd⟩ := hdr obtain ⟨qa, qb, hqa, hqb, hqd⟩ := hdl have he : pa = qa := Option.some.inj (ha.symm.trans hqa) subst qa have hh := hc l hl simpa [treeDist, ha, hb, hqb, ← hd, ← hqd, ha] using hh · rintro ⟨hr, hs⟩ refine ⟨hr, ?_⟩ intro l hl cases hk : pathTo (decode input.1) input.2 with | none => simp [treeDist, hk] | some pk => obtain ⟨pr, hpr⟩ := P _ _ hr obtain ⟨pl, hpl⟩ := P _ _ hl apply hs l hl · exact ⟨pk, pr, hk, hpr, by simp [treeDist, hk, hpr]⟩ · exact ⟨pk, pl, hk, hpl, by simp [treeDist, hk, hpl]⟩ theorem leaf_bool (t : BinTree) (v : Nat) : isLeafValInTree t v = true ↔ isLeafInTree t v := by have E : ∀ t, isEmptyTree t = true ↔ t = BinTree.nil := by intro t cases t <;> simp [isEmptyTree] induction t with | nil => simp [isLeafValInTree, isLeafInTree] | node x l r ihl ihr => simp [isLeafValInTree, isLeafInTree, ihl, ihr, E, and_assoc, or_assoc] theorem leaf_mem (t : BinTree) (v : Nat) : v ∈ leafValuesOf t ↔ isLeafInTree t v := by induction t with | nil => simp [leafValuesOf, isLeafInTree] | node x l r ihl ihr => cases l <;> cases r <;> simp_all [leafValuesOf, isLeafInTree, eq_comm] theorem leaf_path (t : BinTree) (v : Nat) : isLeafInTree t v → ∃ p, pathTo t v = some p := by induction t with | nil => simp [isLeafInTree] | node x l r ihl ihr => intro h by_cases hx : x = v · simp [pathTo, hx] · rcases h with ⟨he, _, _⟩ | hl | hr · exact (hx he).elim · obtain ⟨p, hp⟩ := ihl hl simp [pathTo, hx, hp] · obtain ⟨p, hp⟩ := ihr hr cases hq : pathTo l v <;> simp [pathTo, hx, hp, hq] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem closestLeafValue_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : closestLeafValue_check input result ↔ closestLeafValue_spec input result := by exact root_of_bridges leaf_bool leaf_mem leaf_path input result /-! ### Implementation helpers -/ /-- Nearest leaf inside a subtree as `(distance, value)`, with equal distances resolved by smaller value. -/ def nearestLeafDown : BinTree → Option (Nat × Nat) | BinTree.nil => none | BinTree.node x l r => match nearestLeafDown l, nearestLeafDown r with | none, none => some (0, x) | some p, none => some (p.1 + 1, p.2) | none, some p => some (p.1 + 1, p.2) | some pl, some pr => let p := if pl.1 < pr.1 then pl else if pr.1 < pl.1 then pr else if pl.2 ≤ pr.2 then pl else pr some (p.1 + 1, p.2) /-- Walk the root-to-target path, combining the target-side result with each sibling subtree's nearest leaf. -/ def closestFromPath : BinTree → List Bool → Option (Nat × Nat) | t, [] => nearestLeafDown t | BinTree.nil, _ :: _ => none | BinTree.node _ l r, b :: bs => let child := match b with | false => l | true => r let sibling := match b with | false => r | true => l let down := closestFromPath child bs let side := match nearestLeafDown sibling with | none => none | some p => some (bs.length + 2 + p.1, p.2) match down, side with | none, none => none | some p, none => some p | none, some p => some p | some p, some q => if p.1 < q.1 then some p else if q.1 < p.1 then some q else if p.2 ≤ q.2 then some p else some q /-! ### Main algorithm (impl) -/ /-- Numerals in a level-order serialization denote present node values, so a numeral in an `Option Nat` position elaborates as the wrapped value. -/ instance instOfNatOptionNat (n : Nat) : OfNat (Option Nat) n where ofNat := some n /-- `null` is the absent-node entry of a level-order serialization. -/ abbrev null : Option Nat := none /-- Closest leaf value by a bottom-up nearest-leaf pass followed by a root-to-target path walk, decoding the level-order serialization with the shared `decode` and locating the target with the shared `pathTo`. -/ def findClosestLeaf (input : Input) : Output := let t := decode input.1 match pathTo t input.2 with | none => 0 | some path => match closestFromPath t path with | some p => p.2 | none => 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findClosestLeaf_correct (input : Input) (h : isValidInput input) : closestLeafValue_spec input (findClosestLeaf input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([(some 1), (some 3), (some 2)], 1) #guard isValidInput ([(some 1)], 1) #guard isValidInput ([(some 1), (some 2), (some 3), (some 4), none, none, none, (some 5), none, (some 6)], 2) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([(some 0), (some 1), (some 2)], 1)) #guard !(isValidInput ([(some 1), (some 1), (some 2)], 2)) #guard !(isValidInput ([(some 1), (some 2), (some 3)], 4)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard closestLeafValue_check ([(some 1), (some 3), (some 2)], 1) 2 #guard closestLeafValue_check ([(some 1)], 1) 1 #guard closestLeafValue_check ([(some 1), (some 2), (some 3), (some 4), none, none, none, (some 5), none, (some 6)], 2) 3 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(closestLeafValue_check ([(some 1), (some 3), (some 2)], 1) 1) #guard !(closestLeafValue_check ([(some 1)], 1) 0) #guard !(closestLeafValue_check ([(some 1), (some 2), (some 3), (some 4), none, none, none, (some 5), none, (some 6)], 2) 6) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findClosestLeaf ([1, 3, 2], 1) == 2 #guard findClosestLeaf ([1], 1) == 1 #guard findClosestLeaf ([1, 2, 3, 4, null, null, null, 5, null, 6], 2) == 3 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard closestLeafValue_check ([1, 3, 2], 1) (findClosestLeaf ([1, 3, 2], 1)) #guard closestLeafValue_check ([1], 1) (findClosestLeaf ([1], 1)) #guard closestLeafValue_check ([1, 2, 3, 4, null, null, null, 5, null, 6], 2) (findClosestLeaf ([1, 2, 3, 4, null, null, null, 5, null, 6], 2)) end PClosestLeafInABinaryTree