import Mathlib /-! # Minimum Absolute Difference In Bst Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree. ## Constraints - The number of nodes in the tree is in the range [2, 10^4]. - 0 <= Node.val <= 10^5 - Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/ ## Provided examples - `root = [4, 2, 6, 1, 3]` → `1` - `root = [1, 0, 48, null, null, 12, 49]` → `1` - `root = [5, 4, 7]` → `1` ## Synthesized negative examples - invalid input: `root = [1]` ([structural] a predicate that admits The number of nodes in the tree is in the range [2, 10^4].. one node, below the minimum) - invalid input: `root = [-1, null, 1]` ([structural] a predicate that admits 0 <= Node.val <= 10^5. negative node value where non-negative is required) - invalid input: `root = [100001, 1]` ([structural] a predicate that admits 0 <= Node.val <= 10^5. one past the maximum node value) - `root = [4, 2, 6, 1, 3]` → `-1` is wrong ([structural] bound not required to be achieved. Below any achievable difference for this tree) - `root = [1, 0, 48, null, null, 12, 49]` → `11` is wrong ([structural] minimality stated as achievability alone. 11 is achieved by nodes 1 and 12 but is not least) - `root = [5, 4, 7]` → `2` is wrong ([structural] minimality stated as achievability alone. 2 is attained by nodes 5 and 7 but is not least) -/ namespace PMinimumAbsoluteDifferenceInBst /-! ### Representation -/ /-- Numeric literals at `Option Int` denote `some` of the literal, so frozen node arrays elaborate. -/ instance instOfNatOptionInt (n : Nat) : OfNat (Option Int) n where ofNat := some (OfNat.ofNat n) abbrev Input := List (Option Int) abbrev Output := Int /-! ### Specification helpers -/ /-- The element at index `i` of the array encoding exists and is non-null. -/ def nonNullAt (root : List (Option Int)) (i : Nat) : Bool := match root[i]? with | some (some _) => true | _ => false /-- The node value at index `i`, defaulting to 0 when the node is absent. -/ def valAt (root : List (Option Int)) (i : Nat) : Int := match root[i]? with | some (some v) => v | _ => 0 /-- `j` lies in the subtree rooted at index `r` of the heap-style array encoding. -/ def inSubtree (j r : Nat) : Bool := match j with | 0 => r == 0 | j' + 1 => if j' + 1 == r then true else inSubtree (j' / 2) r termination_by j decreasing_by omega /-- `i` and `j` are distinct non-null indices whose node values have absolute difference `d`. -/ def NodeDistance (root : List (Option Int)) (i j : Nat) (d : Int) : Prop := i ≠ j ∧ ∃ a b : Int, root[i]? = some (some a) ∧ root[j]? = some (some b) ∧ d = |a - b| /-! ### Validity predicate (V) -/ /-- Valid input: non-null root and last entry, non-null parents, 2 to 10^4 non-null nodes valued in [0, 10^5], satisfying the BST order property. -/ def isValidInput (input : Input) : Bool := nonNullAt input 0 && nonNullAt input (input.length - 1) && 2 ≤ input.countP (·.isSome) && input.countP (·.isSome) ≤ 10000 && input.all (fun x => match x with | some v => 0 ≤ v && v ≤ 100000 | none => true) && (List.range input.length).all (fun i => !(nonNullAt input i) || i == 0 || nonNullAt input ((i - 1) / 2)) && (List.range input.length).all (fun i => (List.range input.length).all (fun j => !(nonNullAt input i) || !(nonNullAt input j) || ((!(inSubtree j (2 * i + 1)) || valAt input j < valAt input i) && (!(inSubtree j (2 * i + 2)) || valAt input j > valAt input i)))) /-! ### Ideal specification (P_spec) -/ /-- `result` is the least absolute difference between the values of two distinct nodes of the tree. -/ def minAbsDiffBST_spec (input : Input) (result : Output) : Prop := IsLeast {d : Int | ∃ i j : Nat, NodeDistance input i j d} result /-! ### Decidable specification (P_check) -/ /-- Executable checker for `minAbsDiffBST_spec`: `IsLeast` with the index quantifiers truncated to `List.range input.length`, which `NodeDistance`'s lookup clauses already force. -/ def minAbsDiffBST_check (input : Input) (result : Output) : Bool := decide ((∃ i ∈ List.range input.length, ∃ j ∈ List.range input.length, i ≠ j ∧ nonNullAt input i = true ∧ nonNullAt input j = true ∧ result = |valAt input i - valAt input j|) ∧ (∀ i ∈ List.range input.length, ∀ j ∈ List.range input.length, i ≠ j → nonNullAt input i = true → nonNullAt input j = true → result ≤ |valAt input i - valAt input j|)) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minAbsDiffBST_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minAbsDiffBST_check input result ↔ minAbsDiffBST_spec input result := by have nn (i : Nat) : nonNullAt input i = true ↔ ∃ a, input[i]? = some (some a) := by unfold nonNullAt cases hh : input[i]? with | none => simp | some v => cases v <;> simp have vv (i : Nat) (a : Int) (ha : input[i]? = some (some a)) : valAt input i = a := by simp [valAt,ha] have bd (i : Nat) (a : Int) (ha : input[i]? = some (some a)) : i < input.length := by by_contra hh have hz : input[i]? = none := List.getElem?_eq_none (by omega) simp_all have bridge (d : Int) : (∃ i ∈ List.range input.length, ∃ j ∈ List.range input.length, i ≠ j ∧ nonNullAt input i = true ∧ nonNullAt input j = true ∧ d = |valAt input i - valAt input j|) ↔ ∃ i j, NodeDistance input i j d := by simp only [List.mem_range, nn, NodeDistance] constructor · rintro ⟨i,hi,j,hj,hij,⟨a,ha⟩,⟨b,hb⟩,hd⟩ exact ⟨i,j,hij,a,b,ha,hb,by simpa [vv i a ha,vv j b hb] using hd⟩ · rintro ⟨i,j,hij,a,b,ha,hb,hd⟩ exact ⟨i,bd i a ha,j,bd j b hb,hij,⟨a,ha⟩,⟨b,hb⟩,by simpa [vv i a ha,vv j b hb] using hd⟩ simp only [minAbsDiffBST_check, Bool.decide_coe, decide_eq_true_eq, bridge, minAbsDiffBST_spec, IsLeast, lowerBounds, Set.mem_setOf_eq] constructor · rintro ⟨hm,hu⟩ refine ⟨hm,?_⟩ rintro d ⟨i,j,hij,a,b,ha,hb,rfl⟩ have hh := hu i (List.mem_range.mpr (bd i a ha)) j (List.mem_range.mpr (bd j b hb)) hij ((nn i).mpr ⟨a,ha⟩) ((nn j).mpr ⟨b,hb⟩) simpa [vv i a ha,vv j b hb] using hh · rintro ⟨hm,hu⟩ refine ⟨hm,?_⟩ intro i hi j hj hij hni hnj obtain ⟨a,ha⟩ := (nn i).mp hni obtain ⟨b,hb⟩ := (nn j).mp hnj have hh := hu ⟨i,j,hij,a,b,ha,hb,rfl⟩ simpa [vv i a ha,vv j b hb] using hh /-! ### Implementation helpers -/ /-- Values visited from heap index `i` in left-node-right order, using the array child indices. -/ def inorderValues (root : List (Option Int)) (i : Nat) : List Int := if h : i < root.length then if _ : nonNullAt root i = true then let left := if h₁ : 2 * i + 1 < root.length then if _ : nonNullAt root (2 * i + 1) = true then inorderValues root (2 * i + 1) else [] else [] let right := if h₂ : 2 * i + 2 < root.length then if _ : nonNullAt root (2 * i + 2) = true then inorderValues root (2 * i + 2) else [] else [] left ++ [valAt root i] ++ right else [] else [] termination_by root.length - i decreasing_by all_goals omega /-- Least absolute difference between consecutive values of a list, or 0 when no pair exists. -/ def minimumAdjacentDiff : List Int → Int | [] => 0 | [_] => 0 | a :: b :: rest => min (|a - b|) (minimumAdjacentDiff (b :: rest)) /-! ### Main algorithm (impl) -/ /-- Minimum absolute BST difference by in-order traversal followed by an adjacent-value scan. -/ def getMinimumDifference (input : Input) : Output := let rec scan (prev : Int) (best : Int) : List Int → Int | [] => best | x :: xs => scan x (min best (|prev - x|)) xs match inorderValues input 0 with | a :: b :: rest => scan b (|a - b|) rest | _ => 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem getMinimumDifference_correct (input : Input) (h : isValidInput input) : minAbsDiffBST_spec input (getMinimumDifference input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [4, 2, 6, 1, 3] #guard isValidInput [(some 1), (some 0), (some 48), none, none, (some 12), (some 49)] #guard isValidInput [5, 4, 7] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput [1]) #guard !(isValidInput [(some (-1)), none, (some 1)]) #guard !(isValidInput [100001, 1]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minAbsDiffBST_check [4, 2, 6, 1, 3] 1 #guard minAbsDiffBST_check [(some 1), (some 0), (some 48), none, none, (some 12), (some 49)] 1 #guard minAbsDiffBST_check [5, 4, 7] 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minAbsDiffBST_check [4, 2, 6, 1, 3] (-1)) #guard !(minAbsDiffBST_check [(some 1), (some 0), (some 48), none, none, (some 12), (some 49)] 11) #guard !(minAbsDiffBST_check [5, 4, 7] 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard getMinimumDifference [4, 2, 6, 1, 3] == 1 #guard getMinimumDifference [(some 1), (some 0), (some 48), none, none, (some 12), (some 49)] == 1 #guard getMinimumDifference [5, 4, 7] == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minAbsDiffBST_check [4, 2, 6, 1, 3] (getMinimumDifference [4, 2, 6, 1, 3]) #guard minAbsDiffBST_check [(some 1), (some 0), (some 48), none, none, (some 12), (some 49)] (getMinimumDifference [(some 1), (some 0), (some 48), none, none, (some 12), (some 49)]) #guard minAbsDiffBST_check [5, 4, 7] (getMinimumDifference [5, 4, 7]) end PMinimumAbsoluteDifferenceInBst