import Mathlib /-! # Closest Binary Search Tree Value Ii Given the root of a binary search tree, a target value, and an integer k, return the k values in the BST that are closest to the target. You may return the answer in any order. You are guaranteed to have only one unique set of k values in the BST that are closest to the target. ## Constraints - The number of nodes in the tree is n. - 1 <= k <= n <= 10^4. - 0 <= Node.val <= 10^9 - -10^9 <= target <= 10^9 ## Provided examples - `root = [4, 2, 5, 1, 3], target = 3.714286, k = 2` → `[4, 3]` - `root = [1], target = 0.0, k = 1` → `[1]` - `root = [3, 1, 4, null, 2], target = 0.275, k = 2` → `[1, 2]` ## Synthesized negative examples - invalid input: `root = [1], target = 0.0, k = 0` ([structural] a predicate that admits 1 <= k <= n <= 10^4.. k is one below the stated minimum) - invalid input: `root = [1], target = 0.0, k = 2` ([structural] a predicate that admits 1 <= k <= n <= 10^4.. k exceeds the number of nodes; each parameter alone is legal) - invalid input: `root = [-1], target = 0.0, k = 1` ([structural] a predicate that admits 0 <= Node.val <= 10^9. negative node value where nonnegative is required) - `root = [4, 2, 5, 1, 3], target = 3.714286, k = 2` → `[]` is wrong ([structural] no clause requires exactly k values to be returned. empty list is vacuously from the BST and closest) - `root = [1], target = 0.0, k = 1` → `[0]` is wrong ([structural] output values are not required to be from the BST. 0 is closer to target 0 than 1 yet no node has it) - `root = [3, 1, 4, null, 2], target = 0.275, k = 2` → `[3, 4]` is wrong ([structural] the output is not required to be the closest k values. closest constraint dropped; 3 and 4 are valid BST values) -/ namespace PClosestBinarySearchTreeValueIi /-! ### Representation -/ /-- A binary tree with integer node values; `Int` so invalid negative literals can be formed and rejected. -/ inductive BST where | nil : BST | node : Int → BST → BST → BST deriving DecidableEq, Repr abbrev Input := (BST) × (Rat) × (Nat) abbrev Output := List Nat /-! ### Specification helpers -/ /-- Builds the tree denoted by a level-order serialization, position `i` having children `2i+1` and `2i+2`. -/ def arrayToBST (l : List (Option Int)) : BST := go l.length 0 where go : Nat → Nat → BST | 0, _ => .nil | fuel + 1, i => match l[i]? with | some (some v) => .node v (go fuel (2 * i + 1)) (go fuel (2 * i + 2)) | _ => .nil /-- The node values of a tree in inorder. -/ def BST.values : BST → List Int | .nil => [] | .node v l r => l.values ++ [v] ++ r.values /-- The number of nodes in the tree. -/ def BST.nodeCount (t : BST) : Nat := t.values.length /-- Every node exceeds all values in its left subtree and is below all values in its right subtree. -/ def BST.isSearchTree : BST → Bool | .nil => true | .node v l r => l.values.all (fun x => x < v) && r.values.all (fun x => v < x) && l.isSearchTree && r.isSearchTree /-- Exactly `k` stored values have fewer than `k` strictly closer stored values, i.e. the closest set is unique. -/ def BST.uniqueClosestSet (t : BST) (target : Rat) (k : Nat) : Bool := (t.values.countP fun v => (t.values.countP fun u => |(u : Rat) - target| < |(v : Rat) - target|) < k) = k /-- `v` is the value stored at some node of `t`. -/ def IsNodeValue (t : BST) (v : Nat) : Prop := (v : Int) ∈ t.values /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty BST of at most 10^4 nodes with values in [0, 10^9], 1 ≤ k ≤ node count, target in [-10^9, 10^9], and a unique closest k-set. -/ def isValidInput (input : Input) : Bool := let root := input.1 let target := input.2.1 let k := input.2.2 root.isSearchTree && 1 ≤ root.nodeCount && 1 ≤ k && k ≤ root.nodeCount && root.nodeCount ≤ 10 ^ 4 && root.values.all (fun v => 0 ≤ v && v ≤ 10 ^ 9) && -10 ^ 9 ≤ target && target ≤ 10 ^ 9 && root.uniqueClosestSet target k /-! ### Ideal specification (P_spec) -/ /-- `result` is any ordering of the `k` stored values each having fewer than `k` strictly closer stored values. -/ def closestKValues_spec (input : Input) (result : Output) : Prop := ∃ S : Finset Nat, (S.card = input.2.2 ∧ (∀ v ∈ S, IsNodeValue input.1 v) ∧ result.length = input.2.2 ∧ ∀ v, v ∈ result ↔ v ∈ S) ∧ ∀ v, IsNodeValue input.1 v → (v ∈ S ↔ (input.1.values.countP fun u => |(u : Rat) - input.2.1| < |(v : Rat) - input.2.1|) < input.2.2) /-! ### Decidable specification (P_check) -/ /-- The number of stored values strictly closer to `target` than the value `v` is. -/ def closerValueCount (vals : List Int) (target : Rat) (v : Nat) : Nat := vals.countP fun u => |(u : Rat) - target| < |(v : Rat) - target| /-- Executable checker for `closestKValues_spec`: the exhibited set is the node values with fewer than `k` strictly closer stored values, and `result` must be a length-`k` listing of it. -/ def closestKValues_check (input : Input) (result : Output) : Bool := let root := input.1 let target := input.2.1 let k := input.2.2 let vals := root.values let nodes : List Nat := (vals.filterMap fun x => if 0 ≤ x then some x.toNat else none).dedup let chosen : List Nat := nodes.filter fun v => closerValueCount vals target v < k decide (chosen.length = k) && chosen.all (fun v => decide ((v : Int) ∈ vals)) && decide (result.length = k) && chosen.all (fun v => decide (v ∈ result)) && result.all (fun v => decide (v ∈ chosen)) && nodes.all (fun v => decide (v ∈ chosen ↔ closerValueCount vals target v < k)) /-- The distinct nonnegative stored values, as naturals: exactly the list the checker enumerates. -/ def nodesOf (vals : List Int) : List Nat := (vals.filterMap fun x => if 0 ≤ x then some x.toNat else none).dedup /-- The enumerated values having fewer than `k` strictly closer stored values. -/ def chosenOf (vals : List Int) (target : Rat) (k : Nat) : List Nat := (nodesOf vals).filter fun v => closerValueCount vals target v < k /-- The enumeration is exactly the nonnegative stored values. -/ theorem mem_nodesOf (vals : List Int) (v : Nat) : v ∈ nodesOf vals ↔ (v : Int) ∈ vals := by simp only [nodesOf, List.mem_dedup, List.mem_filterMap] constructor · rintro ⟨x, hx, hfx⟩ by_cases hx0 : 0 ≤ x · rw [if_pos hx0] at hfx have hv : (v : Int) = x := by rw [← Option.some.inj hfx, Int.toNat_of_nonneg hx0] rw [hv] exact hx · rw [if_neg hx0] at hfx simp at hfx · intro hv refine ⟨(v : Int), hv, ?_⟩ rw [if_pos (Int.natCast_nonneg v), Int.toNat_natCast] theorem nodesOf_nodup (vals : List Int) : (nodesOf vals).Nodup := List.nodup_dedup _ theorem chosenOf_nodup (vals : List Int) (target : Rat) (k : Nat) : (chosenOf vals target k).Nodup := List.Nodup.filter _ (nodesOf_nodup vals) /-- Membership in the checker's deterministic witness, spelled with the specification's own count. -/ theorem mem_chosenOf (vals : List Int) (target : Rat) (k : Nat) (v : Nat) : v ∈ chosenOf vals target k ↔ ((v : Int) ∈ vals ∧ (vals.countP fun u => |(u : Rat) - target| < |(v : Rat) - target|) < k) := by simp only [chosenOf, List.mem_filter, mem_nodesOf, closerValueCount, decide_eq_true_eq] /-- The checker with its `let`s substituted, so `rw` can reach the witness. -/ theorem check_eq (input : Input) (result : Output) : closestKValues_check input result = (decide ((chosenOf input.1.values input.2.1 input.2.2).length = input.2.2) && (chosenOf input.1.values input.2.1 input.2.2).all (fun v => decide ((v : Int) ∈ input.1.values)) && decide (result.length = input.2.2) && (chosenOf input.1.values input.2.1 input.2.2).all (fun v => decide (v ∈ result)) && result.all (fun v => decide (v ∈ chosenOf input.1.values input.2.1 input.2.2)) && (nodesOf input.1.values).all (fun v => decide (v ∈ chosenOf input.1.values input.2.1 input.2.2 ↔ closerValueCount input.1.values input.2.1 v < input.2.2))) := rfl /-- On valid input the checker accepts exactly the specified outputs. -/ theorem closestKValues_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : closestKValues_check input result ↔ closestKValues_spec input result := by rw [check_eq] unfold closestKValues_spec IsNodeValue closerValueCount simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, and_assoc] constructor · rintro ⟨hlen, hsub, hrlen, hcr, hrc, -⟩ refine ⟨(chosenOf input.1.values input.2.1 input.2.2).toFinset, ?_, ?_, hrlen, ?_, ?_⟩ · rw [List.toFinset_card_of_nodup (chosenOf_nodup _ _ _)] exact hlen · intro v hv exact hsub v (List.mem_toFinset.mp hv) · intro v exact ⟨fun hv => List.mem_toFinset.mpr (hrc v hv), fun hv => hcr v (List.mem_toFinset.mp hv)⟩ · intro v hv rw [List.mem_toFinset, mem_chosenOf] exact and_iff_right hv · rintro ⟨S, hcard, hSnode, hrlen, hrS, hSchar⟩ have hSeq : ∀ v : Nat, v ∈ S ↔ v ∈ chosenOf input.1.values input.2.1 input.2.2 := by intro v rw [mem_chosenOf] exact ⟨fun hv => ⟨hSnode v hv, (hSchar v (hSnode v hv)).mp hv⟩, fun hv => (hSchar v hv.1).mpr hv.2⟩ have hfin : (chosenOf input.1.values input.2.1 input.2.2).toFinset = S := by ext v rw [List.mem_toFinset, ← hSeq] refine ⟨?_, ?_, hrlen, ?_, ?_, ?_⟩ · rw [← List.toFinset_card_of_nodup (chosenOf_nodup input.1.values input.2.1 input.2.2), hfin] exact hcard · intro v hv exact ((mem_chosenOf _ _ _ v).mp hv).1 · intro v hv exact (hrS v).mpr ((hSeq v).mpr hv) · intro v hv exact (hSeq v).mp ((hrS v).mp hv) · intro v hv rw [mem_chosenOf] exact and_iff_right ((mem_nodesOf _ v).mp hv) /-! ### Implementation helpers -/ /-- The node values of the tree in inorder, collected with a tail-recursive accumulator in O(n). -/ def valuesLinear (t : BST) : List Int := go t [] where go : BST → List Int → List Int | .nil, acc => acc | .node v l r, acc => go l (v :: go r acc) /-- Shrink the sorted range `vals[lo, hi)` to the `k` values closest to `target` by repeatedly dropping the endpoint with the larger distance. -/ def closestWindow (vals : Array Int) (target : Rat) (k lo hi : Nat) : List Int := if h : hi - lo ≤ k then (vals.toList.drop lo).take (hi - lo) else if |(vals[lo]! : Rat) - target| ≤ |(vals[hi - 1]! : Rat) - target| then closestWindow vals target k lo (hi - 1) else closestWindow vals target k (lo + 1) hi termination_by hi - lo decreasing_by all_goals omega /-- Order the sorted range `vals[lo, hi)` by increasing distance to `target`, moving the farther endpoint onto the accumulator. -/ def orderByDistance (vals : Array Int) (target : Rat) (lo hi : Nat) (acc : List Int) : List Int := if h : hi ≤ lo then acc else if |(vals[lo]! : Rat) - target| < |(vals[hi - 1]! : Rat) - target| then orderByDistance vals target lo (hi - 1) (vals[hi - 1]! :: acc) else orderByDistance vals target (lo + 1) hi (vals[lo]! :: acc) termination_by hi - lo decreasing_by all_goals omega /-! ### Main algorithm (impl) -/ /-- The `k` closest values by linear inorder traversal, a two-pointer shrink to the closest window, and an endpoint merge ordering by distance to the target. -/ def closestKValuesBST (input : Input) : Output := let root := input.1 let target := input.2.1 let k := input.2.2 let arr := (valuesLinear root).toArray let window := (closestWindow arr target k 0 arr.size).toArray (orderByDistance window target 0 window.size []).map Int.toNat /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem closestKValuesBST_correct (input : Input) (h : isValidInput input) : closestKValues_spec input (closestKValuesBST input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ((arrayToBST [(some 4), (some 2), (some 5), (some 1), (some 3)]), 3.714286, 2) #guard isValidInput ((arrayToBST [(some 1)]), 0.0, 1) #guard isValidInput ((arrayToBST [(some 3), (some 1), (some 4), none, (some 2)]), 0.275, 2) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ((arrayToBST [(some 1)]), 0.0, 0)) #guard !(isValidInput ((arrayToBST [(some 1)]), 0.0, 2)) #guard !(isValidInput ((arrayToBST [(some (-1))]), 0.0, 1)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard closestKValues_check ((arrayToBST [(some 4), (some 2), (some 5), (some 1), (some 3)]), 3.714286, 2) [4, 3] #guard closestKValues_check ((arrayToBST [(some 1)]), 0.0, 1) [1] #guard closestKValues_check ((arrayToBST [(some 3), (some 1), (some 4), none, (some 2)]), 0.275, 2) [1, 2] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(closestKValues_check ((arrayToBST [(some 4), (some 2), (some 5), (some 1), (some 3)]), 3.714286, 2) []) #guard !(closestKValues_check ((arrayToBST [(some 1)]), 0.0, 1) [0]) #guard !(closestKValues_check ((arrayToBST [(some 3), (some 1), (some 4), none, (some 2)]), 0.275, 2) [3, 4]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard closestKValuesBST (arrayToBST [(some 4), (some 2), (some 5), (some 1), (some 3)], 3.714286, 2) == [4, 3] #guard closestKValuesBST (arrayToBST [(some 1)], 0.0, 1) == [1] #guard closestKValuesBST (arrayToBST [(some 3), (some 1), (some 4), none, (some 2)], 0.275, 2) == [1, 2] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard closestKValues_check (arrayToBST [(some 4), (some 2), (some 5), (some 1), (some 3)], 3.714286, 2) (closestKValuesBST (arrayToBST [(some 4), (some 2), (some 5), (some 1), (some 3)], 3.714286, 2)) #guard closestKValues_check (arrayToBST [(some 1)], 0.0, 1) (closestKValuesBST (arrayToBST [(some 1)], 0.0, 1)) #guard closestKValues_check (arrayToBST [(some 3), (some 1), (some 4), none, (some 2)], 0.275, 2) (closestKValuesBST (arrayToBST [(some 3), (some 1), (some 4), none, (some 2)], 0.275, 2)) end PClosestBinarySearchTreeValueIi