import Mathlib /-! # Validate Binary Search Tree Given the root of a binary tree, determine if it is a valid binary search tree (BST). A valid BST is defined as follows: The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees. ## Constraints - The number of nodes in the tree is in the range [1, 10^4]. - -2^31 <= Node.val <= 2^31 - 1 ## Provided examples - `root = [2, 1, 3]` → `true` - `root = [5, 1, 4, null, null, 3, 6]` → `false` - `root = [1]` → `true` ## Synthesized negative examples - invalid input: `root = []` ([structural] a predicate that admits The number of nodes in the tree is in the range [1, 10^4].. empty tree where at least one node is required) - invalid input: `root = [-2147483649]` ([structural] a predicate that admits -2^31 <= Node.val <= 2^31 - 1. one below the stated minimum value) - invalid input: `root = [2147483648]` ([structural] a predicate that admits -2^31 <= Node.val <= 2^31 - 1. one above the stated maximum value) - `root = [2, 1, 3]` → `false` is wrong ([structural] nothing requires a true answer for a valid tree. always false passes a spec with no positive-case requirement) - `root = [5, 1, 4, null, null, 3, 6]` → `true` is wrong ([structural] missing the requirement that every node in the right subtree be greater than the node. Only left-child ordering checked, right subtree not required to exceed root.) - `root = [1]` → `false` is wrong ([structural] valid trees are not required to be accepted. false passes a spec that only rejects invalid trees) -/ namespace PValidateBinarySearchTree /-! ### Representation -/ /-- A binary tree with values of type `α`. -/ inductive BinTree (α : Type) where | nil | node (value : α) (left right : BinTree α) abbrev Input := BinTree Int abbrev Output := Bool /-! ### Specification helpers -/ /-- The number of nodes in a binary tree. -/ def nodeCount {α : Type} : BinTree α → Nat | .nil => 0 | .node _ left right => 1 + nodeCount left + nodeCount right /-- Whether every node value lies in the closed interval `[lo, hi]`. -/ def nodeValuesInRange (lo hi : Int) : BinTree Int → Bool | .nil => true | .node value left right => decide (lo ≤ value ∧ value ≤ hi) && nodeValuesInRange lo hi left && nodeValuesInRange lo hi right /-- `treeAll p t` holds when `p` holds at every node of `t`. -/ def treeAll {α : Type} (p : α → Prop) : BinTree α → Prop | .nil => True | .node value left right => p value ∧ treeAll p left ∧ treeAll p right /-- `IsBST t` holds when every node strictly separates its subtrees, recursively. -/ def IsBST : BinTree Int → Prop | .nil => True | .node value left right => treeAll (fun x => x < value) left ∧ treeAll (fun x => value < x) right ∧ IsBST left ∧ IsBST right /-- Build the subtree at level-order index `index`, bounding recursion by `fuel`. -/ def rootListSubtree (values : List (Option Int)) (index : Nat) : Nat → BinTree Int | 0 => .nil | fuel + 1 => match values[index]? with | some (some value) => .node value (rootListSubtree values (2 * index + 1) fuel) (rootListSubtree values (2 * index + 2) fuel) | _ => .nil /-- Build a binary tree from a level-order list with `none` for missing nodes. -/ def rootListToTree (values : List (Option Int)) : BinTree Int := rootListSubtree values 0 values.length /-! ### Validity predicate (V) -/ /-- Valid input has `1` to `10^4` nodes and only signed 32-bit values. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ nodeCount input ∧ nodeCount input ≤ (10 : Nat) ^ 4) && nodeValuesInRange (-2147483648) 2147483647 input /-! ### Ideal specification (P_spec) -/ /-- The result is true exactly when the input satisfies the recursive BST condition. -/ def isValidBst_spec (input : Input) (result : Output) : Prop := result ↔ IsBST input /-! ### Decidable specification (P_check) -/ /-- Boolean test: `p` holds at every node of `t`. -/ def treeAllB {α : Type} (p : α → Bool) : BinTree α → Bool | .nil => true | .node value left right => p value && treeAllB p left && treeAllB p right /-- Boolean version of the recursive BST predicate, mirroring `IsBST`. -/ def isBSTBool : BinTree Int → Bool | .nil => true | .node value left right => treeAllB (fun x => decide (x < value)) left && treeAllB (fun x => decide (value < x)) right && isBSTBool left && isBSTBool right /-- Executable checker obtained mechanically from the specification. -/ def isValidBst_check (input : Input) (result : Output) : Bool := result == isBSTBool input theorem root_of_bridges (bridge : ∀ t : BinTree Int, isBSTBool t = true ↔ IsBST t) (input : Input) (result : Output) : isValidBst_check input result ↔ isValidBst_spec input result := by unfold isValidBst_check isValidBst_spec rw [← bridge input] cases result <;> cases isBSTBool input <;> simp theorem all_reflect {α : Type} (p : α → Prop) [DecidablePred p] (t : BinTree α) : treeAllB (fun x => decide (p x)) t = true ↔ treeAll p t := by induction t with | nil => simp [treeAllB, treeAll] | node value left right ihl ihr => simp [treeAllB, treeAll, ihl, ihr, and_assoc] theorem bst_reflect (t : BinTree Int) : isBSTBool t = true ↔ IsBST t := by induction t with | nil => simp [isBSTBool, IsBST] | node value left right ihl ihr => simp [isBSTBool, IsBST, all_reflect, ihl, ihr, and_assoc] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem isValidBst_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : isValidBst_check input result ↔ isValidBst_spec input result := by exact root_of_bridges bst_reflect input result /-! ### Implementation helpers -/ /-- Whether every node of the subtree lies strictly within the optional bounds `lo < value < hi` and both children are valid with the tightened bounds. -/ def validateBstRange (lo hi : Option Int) : BinTree Int → Bool | .nil => true | .node value left right => (match lo with | some l => decide (l < value) | none => true) && (match hi with | some h => decide (value < h) | none => true) && validateBstRange lo (some value) left && validateBstRange (some value) hi right /-! ### Main algorithm (impl) -/ /-- BST validation by depth-first traversal threading a strict allowed range, visiting each node once. -/ def validateBst (input : Input) : Output := validateBstRange none none input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem validateBst_correct (input : Input) (h : isValidInput input) : isValidBst_spec input (validateBst input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (rootListToTree [(some 2), (some 1), (some 3)]) #guard isValidInput (rootListToTree [(some 5), (some 1), (some 4), none, none, (some 3), (some 6)]) #guard isValidInput (rootListToTree [(some 1)]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (rootListToTree [])) #guard !(isValidInput (rootListToTree [(some (-2147483649))])) #guard !(isValidInput (rootListToTree [(some 2147483648)])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard isValidBst_check (rootListToTree [(some 2), (some 1), (some 3)]) true #guard isValidBst_check (rootListToTree [(some 5), (some 1), (some 4), none, none, (some 3), (some 6)]) false #guard isValidBst_check (rootListToTree [(some 1)]) true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(isValidBst_check (rootListToTree [(some 2), (some 1), (some 3)]) false) #guard !(isValidBst_check (rootListToTree [(some 5), (some 1), (some 4), none, none, (some 3), (some 6)]) true) #guard !(isValidBst_check (rootListToTree [(some 1)]) false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard validateBst (rootListToTree [(some 2), (some 1), (some 3)]) == true #guard validateBst (rootListToTree [(some 5), (some 1), (some 4), none, none, (some 3), (some 6)]) == false #guard validateBst (rootListToTree [(some 1)]) == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard isValidBst_check (rootListToTree [(some 2), (some 1), (some 3)]) (validateBst (rootListToTree [(some 2), (some 1), (some 3)])) #guard isValidBst_check (rootListToTree [(some 5), (some 1), (some 4), none, none, (some 3), (some 6)]) (validateBst (rootListToTree [(some 5), (some 1), (some 4), none, none, (some 3), (some 6)])) #guard isValidBst_check (rootListToTree [(some 1)]) (validateBst (rootListToTree [(some 1)])) end PValidateBinarySearchTree