import Mathlib /-! # Closest Binary Search Tree Value Given the root of a binary search tree and a target value, return the value in the BST that is closest to the target. If there are multiple answers, print the smallest. ## Constraints - The number of nodes in the tree is in the range [1, 10^4]. - 0 <= Node.val <= 10^9 - -10^9 <= target <= 10^9 ## Provided examples - `root = [4, 2, 5, 1, 3], target = 3.714286` → `4` - `root = [1], target = 4.428571` → `1` - `root = [1], target = 1.0` → `1` ## Synthesized negative examples - invalid input: `root = [], target = 0.0` ([structural] a predicate that admits The number of nodes in the tree is in the range [1, 10^4].. empty tree violates the minimum node count) - invalid input: `root = [-1], target = 0.0` ([structural] a predicate that admits 0 <= Node.val <= 10^9. one below the lower bound on Node.val) - invalid input: `root = [1000000001], target = 0.0` ([structural] a predicate that admits 0 <= Node.val <= 10^9. one above the upper bound on Node.val) - `root = [4, 2, 5, 1, 3], target = 3.714286` → `2` is wrong ([structural] The specification requires only that some node value be returned, not that it be closest.. 2 is a node value but farther from target than 4.) - `root = [1], target = 4.428571` → `4` is wrong ([structural] The answer is not required to be a value in the tree; the closest integer to the target is returned.. 4 is closest to target but not a node value.) - `root = [1], target = 1.0` → `2` is wrong ([structural] the result differs from the required one in at least one position. amended 2026-08-18: hand-authored to top the layer up to 3; wrong output is a shape-preserving mutation of the screened answer) -/ namespace PClosestBinarySearchTreeValue /-! ### Representation -/ /-- A binary tree with integer node values, the shape the serialized input denotes. -/ inductive BSTree where | leaf : BSTree | node : Int → BSTree → BSTree → BSTree deriving Repr, BEq abbrev Input := (BSTree) × (Float) abbrev Output := Int /-! ### Specification helpers -/ /-- `intToFloat v` is the integer `v` viewed as a floating-point number. -/ def intToFloat : Int → Float | Int.ofNat n => Float.ofNat n | Int.negSucc n => -Float.ofNat (n + 1) /-- `parseBSTree l` is the tree whose level-order serialization is `l`. -/ def parseBSTree (l : List Int) : BSTree := go l.toArray 0 where /-- `go a i` is the subtree rooted at level-order index `i` of `a`. -/ go (a : Array Int) (i : Nat) : BSTree := if h : i < a.size then .node a[i] (go a (2 * i + 1)) (go a (2 * i + 2)) else .leaf termination_by a.size - i decreasing_by · omega · omega /-- `IsValueInTree t v` holds when the value `v` is stored at some node of `t`. -/ def IsValueInTree : BSTree → Int → Prop | .leaf, _ => False | .node x l r, v => x = v ∨ IsValueInTree l v ∨ IsValueInTree r v /-- `countNodes t` is the number of nodes of `t`. -/ def countNodes : BSTree → Nat | .leaf => 0 | .node _ l r => countNodes l + countNodes r + 1 /-- `inorder t` is the in-order traversal of `t` as a list of values. -/ def inorder : BSTree → List Int | .leaf => [] | .node x l r => inorder l ++ x :: inorder r /-- `strictlyIncreasing l` holds when each entry of `l` is less than the next. -/ def strictlyIncreasing : List Int → Bool | [] => true | [_] => true | x :: y :: rest => x < y && strictlyIncreasing (y :: rest) /-- `isBST t` holds when `t` has the binary search tree property. -/ def isBST (t : BSTree) : Bool := strictlyIncreasing (inorder t) /-- `valuesInRange t` holds when every node value of `t` is between 0 and 10^9. -/ def valuesInRange : BSTree → Bool | .leaf => true | .node x l r => 0 ≤ x && x ≤ 1000000000 && valuesInRange l && valuesInRange r /-! ### Validity predicate (V) -/ /-- Valid input: a BST with 1 to 10^4 nodes, values in [0, 10^9], target in [-10^9, 10^9]. -/ def isValidInput (input : Input) : Bool := isBST input.1 && 1 ≤ countNodes input.1 && countNodes input.1 ≤ 10000 && valuesInRange input.1 && -1e9 ≤ input.2 && input.2 ≤ 1e9 /-! ### Ideal specification (P_spec) -/ /-- `result` is a value of the tree minimizing the distance to the target, smallest on ties. -/ def closestValue_spec (input : Input) (result : Output) : Prop := IsValueInTree input.1 result ∧ ∀ v : Int, IsValueInTree input.1 v → |(result : ℚ) - input.2.toRat0| ≤ |(v : ℚ) - input.2.toRat0| ∧ (|(result : ℚ) - input.2.toRat0| = |(v : ℚ) - input.2.toRat0| → result ≤ v) /-! ### Decidable specification (P_check) -/ /-- `distToTarget input v` is the distance between the node value `v` and the target. -/ def distToTarget (input : Input) (v : Int) : ℚ := |(v : ℚ) - input.2.toRat0| /-- Executable checker for `closestValue_spec`, quantifying over the in-order node values. -/ def closestValue_check (input : Input) (result : Output) : Bool := (inorder input.1).contains result && (inorder input.1).all fun v => decide (distToTarget input result ≤ distToTarget input v) && decide (distToTarget input v ≤ distToTarget input result → result ≤ v) theorem cb_mem_inorder (t : BSTree) (v : Int) : v ∈ inorder t ↔ IsValueInTree t v := by induction t with | leaf => simp [inorder, IsValueInTree] | node x l r ihl ihr => simp only [inorder, IsValueInTree, List.mem_append, List.mem_cons, ihl, ihr, @eq_comm _ v x] tauto /-- On valid input the checker accepts exactly the specified outputs. -/ theorem closestValue_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : closestValue_check input result ↔ closestValue_spec input result := by simp only [closestValue_check, closestValue_spec, Bool.and_eq_true, List.contains_iff_mem, List.all_eq_true, decide_eq_true_eq, cb_mem_inorder, distToTarget] constructor · rintro ⟨hm, hall⟩ refine ⟨hm, fun v hv => ?_⟩ obtain ⟨h1, h2⟩ := hall v hv exact ⟨h1, fun he => h2 (le_of_eq he.symm)⟩ · rintro ⟨hm, hall⟩ refine ⟨hm, fun v hv => ?_⟩ obtain ⟨h1, h2⟩ := hall v hv exact ⟨h1, fun hle => h2 (le_antisymm h1 hle)⟩ /-! ### Implementation helpers -/ /-- `go input t best` descends one search path of `t`, keeping `best` as the closest value seen so far, smallest on ties. -/ def go (input : Input) (t : BSTree) (best : Int) : Int := match t with | .leaf => best | .node x l r => let d := distToTarget input x let b := distToTarget input best let best' := if d < b || (d == b && x < best) then x else best if intToFloat x == input.2 then best' else if input.2 < intToFloat x then go input l best' else go input r best' /-! ### Main algorithm (impl) -/ /-- Closest value by binary-search descent through the BST, O(h) visited nodes. -/ def findClosestValue (input : Input) : Output := match input.1 with | .leaf => 0 | .node x _ _ => go input input.1 x /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findClosestValue_correct (input : Input) (h : isValidInput input) : closestValue_spec input (findClosestValue input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (parseBSTree [4, 2, 5, 1, 3], 3.714286) #guard isValidInput (parseBSTree [1], 4.428571) #guard isValidInput (parseBSTree [1], 1.0) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (parseBSTree [], 0.0)) #guard !(isValidInput (parseBSTree [(-1)], 0.0)) #guard !(isValidInput (parseBSTree [1000000001], 0.0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard closestValue_check ((parseBSTree [4, 2, 5, 1, 3]), 3.714286) 4 #guard closestValue_check ((parseBSTree [1]), 4.428571) 1 #guard closestValue_check ((parseBSTree [1]), 1.0) 1 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(closestValue_check ((parseBSTree [4, 2, 5, 1, 3]), 3.714286) 2) #guard !(closestValue_check ((parseBSTree [1]), 4.428571) 4) #guard !(closestValue_check ((parseBSTree [1]), 1.0) 2) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findClosestValue (parseBSTree [4, 2, 5, 1, 3], 3.714286) == 4 #guard findClosestValue (parseBSTree [1], 4.428571) == 1 #guard findClosestValue (parseBSTree [1], 1.0) == 1 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard closestValue_check (parseBSTree [4, 2, 5, 1, 3], 3.714286) (findClosestValue (parseBSTree [4, 2, 5, 1, 3], 3.714286)) #guard closestValue_check (parseBSTree [1], 4.428571) (findClosestValue (parseBSTree [1], 4.428571)) #guard closestValue_check (parseBSTree [1], 1.0) (findClosestValue (parseBSTree [1], 1.0)) end PClosestBinarySearchTreeValue