import Mathlib /-! # Unique Binary Search Trees Given an integer n, return the number of structurally unique BST's (binary search trees) which has exactly n nodes of unique values from 1 to n. ## Constraints - 1 <= n <= 19 ## Provided examples - `n = 3` → `5` - `n = 1` → `1` - `n = 2` → `2` ## Synthesized negative examples - invalid input: `n = 0` ([structural] a predicate that admits 1 <= n <= 19. one below the stated minimum) - invalid input: `n = 20` ([structural] a predicate that admits 1 <= n <= 19. one above the stated maximum) - invalid input: `n = 100` ([structural] a predicate that admits 1 <= n <= 19. an order of magnitude past the maximum) - `n = 3` → `2` is wrong ([structural] uses n-1 nodes in the count. Catalan(2) is 2, a specification for n-1 nodes) - `n = 1` → `2` is wrong ([structural] exactly n nodes is not enforced, allowing at most n. counts empty tree as well as single node) - `n = 2` → `3` is wrong ([structural] exactness omitted; answer may be one off. 3 is one greater than the true count 2) -/ namespace PUniqueBinarySearchTrees abbrev Input := Nat abbrev Output := Nat /-! ### Specification helpers -/ /-- The left-root-right inorder traversal of a labeled binary tree. -/ def bstInorder : BinaryTree Nat → List Nat | .nil => [] | .node value left right => bstInorder left ++ [value] ++ bstInorder right /-- `t` is a binary search tree whose inorder traversal is exactly `[1, 2, ..., n]`. -/ def IsBSTOfRange (t : BinaryTree Nat) (n : Nat) : Prop := bstInorder t = (List.range n).map (· + 1) /-! ### Validity predicate (V) -/ /-- Valid input: the stated bounds `1 ≤ n ≤ 19`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input && input ≤ 19 /-! ### Ideal specification (P_spec) -/ /-- `result` is the size of a finite collection containing exactly the BSTs over `1..input`. -/ def numTrees_spec (input : Input) (result : Output) : Prop := ∃ trees : Finset (BinaryTree Nat), trees.card = result ∧ ∀ tree : BinaryTree Nat, tree ∈ trees ↔ IsBSTOfRange tree input /-! ### Decidable specification (P_check) -/ /-- All trees whose inorder traversal is `l`, built by choosing the root position; `fuel` bounds the recursion and `l.length + 1` always suffices. -/ def treesWithInorderFuel (fuel : Nat) (l : List Nat) : List (BinaryTree Nat) := match fuel, l with | 0, _ => [] | _, [] => [.nil] | fuel + 1, _ :: _ => (List.range l.length).flatMap fun i => (treesWithInorderFuel fuel (l.take i)).flatMap fun left => (treesWithInorderFuel fuel (l.drop (i + 1))).map fun right => .node (l.getD i 0) left right /-- The finite list of all labeled binary trees whose inorder traversal is exactly `l`. -/ def treesWithInorder (l : List Nat) : List (BinaryTree Nat) := treesWithInorderFuel (l.length + 1) l /-- Every tree satisfying `IsBSTOfRange n` appears in this list, and every tree in it satisfies `IsBSTOfRange n`. -/ def allBSTs (n : Nat) : List (BinaryTree Nat) := treesWithInorder ((List.range n).map (· + 1)) /-- Inorder traversal of a binary tree: left subtree, root label, right subtree. -/ def treeInorder : BinaryTree Nat → List Nat | .nil => [] | .node v left right => treeInorder left ++ v :: treeInorder right /-- Structural equality on labeled binary trees. -/ def treeEq : BinaryTree Nat → BinaryTree Nat → Bool | .nil, .nil => true | .node v1 l1 r1, .node v2 l2 r2 => v1 == v2 && treeEq l1 l2 && treeEq r1 r2 | _, _ => false /-- Executable checker for `numTrees_spec`: verify that the enumerated collection contains only trees whose inorder traversal is exactly `1..input`, that each such tree occurs exactly once, and that the collection's cardinality is `result`. -/ def numTrees_check (input : Input) (result : Output) : Bool := let labels := (List.range input).map (· + 1) let trees := allBSTs input decide (∀ t ∈ trees, treeInorder t = labels) && trees.all (fun t => (trees.filter (fun s => treeEq s t)).length == 1) && trees.length == result theorem enum_nodup (sound : ∀ (f : Nat) (l : List Nat) (t : BinaryTree Nat), t ∈ treesWithInorderFuel f l → bstInorder t = l) : ∀ (f : Nat) (l : List Nat), (treesWithInorderFuel f l).Nodup := by intro f induction f with | zero => intro l simp [treesWithInorderFuel] | succ f ih => intro l cases l with | nil => simp [treesWithInorderFuel] | cons a l => simp only [treesWithInorderFuel] rw [List.nodup_flatMap] constructor · intro i hi rw [List.nodup_flatMap] constructor · intro left hleft exact (ih (List.drop (i + 1) (a :: l))).map fun _ _ h => by injection h · exact (ih (List.take i (a :: l))).imp fun {left₁ left₂} hne => by simp only [Function.onFun] rw [List.disjoint_left] intro t ht₁ ht₂ rcases List.mem_map.1 ht₁ with ⟨right₁, hright₁, rfl⟩ rcases List.mem_map.1 ht₂ with ⟨right₂, hright₂, heq⟩ apply hne have hleft : left₂ = left₁ := by injection heq exact hleft.symm · rw [List.pairwise_iff_getElem] intro i j hi hj hij simp only [List.length_range] at hi hj simp only [List.getElem_range, Function.onFun] rw [List.disjoint_left] intro t hti htj rcases List.mem_flatMap.1 hti with ⟨lefti, hlefti, hti⟩ rcases List.mem_map.1 hti with ⟨righti, hrighti, rfl⟩ rcases List.mem_flatMap.1 htj with ⟨leftj, hleftj, htj⟩ rcases List.mem_map.1 htj with ⟨rightj, hrightj, heq⟩ have hleft : lefti = leftj := by have hleft' : leftj = lefti := by injection heq exact hleft'.symm have htakes : List.take i (a :: l) = List.take j (a :: l) := by calc List.take i (a :: l) = bstInorder lefti := (sound f _ lefti hlefti).symm _ = bstInorder leftj := congrArg bstInorder hleft _ = List.take j (a :: l) := sound f _ leftj hleftj have hil : i ≤ (a :: l).length := Nat.le_of_lt hi have hjl : j ≤ (a :: l).length := Nat.le_of_lt hj have heqij : i = j := by have hlen := congrArg List.length htakes rw [List.length_take_of_le hil, List.length_take_of_le hjl] at hlen exact hlen exact (Nat.ne_of_lt hij) heqij theorem inorder_eq (t : BinaryTree Nat) : treeInorder t = bstInorder t := by induction t with | nil => rfl | node v l r hl hr => simp [treeInorder, bstInorder, hl, hr] theorem treeEq_eq (s t : BinaryTree Nat) : treeEq s t = decide (s = t) := by induction s generalizing t with | nil => cases t <;> simp [treeEq] | node v l r hl hr => cases t <;> simp [treeEq, hl, hr, Bool.and_assoc, Bool.beq_eq_decide_eq] theorem root_of_bridges (hm : ∀ n t, t ∈ allBSTs n ↔ IsBSTOfRange t n) (hn : ∀ n, (allBSTs n).Nodup) (input result : Nat) : numTrees_check input result ↔ numTrees_spec input result := by classical have hs : ∀ t ∈ allBSTs input, treeInorder t = (List.range input).map (· + 1) := by intro t ht rw [inorder_eq] exact (hm input t).mp ht have hc : ∀ t ∈ allBSTs input, ((allBSTs input).filter (fun s => treeEq s t)).length = 1 := by intro t ht simpa only [treeEq_eq, List.count_eq_length_filter, Bool.beq_eq_decide_eq] using (List.count_eq_one_of_mem (hn input) ht) have he : numTrees_spec input result ↔ (allBSTs input).length = result := by constructor · rintro ⟨s, hs, hmem⟩ have e : s = (allBSTs input).toFinset := by ext t simp only [List.mem_toFinset, hmem, hm] simpa [e, List.toFinset_card_of_nodup (hn input)] using hs · intro hr exact ⟨(allBSTs input).toFinset, by simpa [List.toFinset_card_of_nodup (hn input)] using hr, by simpa using hm input⟩ simp only [numTrees_check, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, beq_iff_eq] exact ⟨fun hh => he.mpr hh.2, fun hh => ⟨⟨hs, hc⟩, he.mp hh⟩⟩ theorem enum_sound (f : Nat) (l : List Nat) (t : BinaryTree Nat) (ht : t ∈ treesWithInorderFuel f l) : bstInorder t = l := by induction f generalizing l t with | zero => simp [treesWithInorderFuel] at ht | succ f ih => cases l with | nil => have e : t = .nil := by simpa [treesWithInorderFuel] using ht subst t rfl | cons a xs => simp only [treesWithInorderFuel, List.mem_flatMap, List.mem_range, List.mem_map] at ht obtain ⟨i, hi, left, hl, right, hr, rfl⟩ := ht simp only [bstInorder, ih _ _ hl, ih _ _ hr, List.append_assoc, List.singleton_append] rw [List.getD_eq_getElem (a :: xs) 0 hi, List.getElem_cons_drop hi, List.take_append_drop] theorem enum_step (f : Nat) (l : List Nat) (hl : l ≠ []) : treesWithInorderFuel (f + 1) l = (List.range l.length).flatMap (fun i => (treesWithInorderFuel f (l.take i)).flatMap (fun left => (treesWithInorderFuel f (l.drop (i + 1))).map (fun right => BinaryTree.node (l.getD i 0) left right))) := by cases l <;> simp_all [treesWithInorderFuel] theorem enum_complete (t : BinaryTree Nat) (f : Nat) (hf : (bstInorder t).length < f) : t ∈ treesWithInorderFuel f (bstInorder t) := by induction t generalizing f with | nil => cases f <;> simp_all [bstInorder, treesWithInorderFuel] | node v left right ihl ihr => cases f with | zero => omega | succ f => simp only [bstInorder, List.append_assoc, List.singleton_append] at hf ⊢ rw [enum_step f _ (by simp)] simp only [List.mem_flatMap, List.mem_range, List.mem_map] refine ⟨(bstInorder left).length, by simp, left, ?_, right, ?_, ?_⟩ · simpa using ihl f (by simp only [List.length_append, List.length_cons] at hf; omega) · simpa [List.drop_append, List.drop_of_length_le (Nat.le_add_right _ _)] using ihr f (by simp only [List.length_append, List.length_cons] at hf; omega) · simp [List.getD_append_right] theorem enum_membership (f : Nat) (l : List Nat) (hf : l.length < f) (t : BinaryTree Nat) : t ∈ treesWithInorderFuel f l ↔ bstInorder t = l := by constructor · exact enum_sound f l t · intro ht subst l exact enum_complete t f hf /-- On valid input the checker accepts exactly the specified outputs. -/ theorem numTrees_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : numTrees_check input result ↔ numTrees_spec input result := by apply root_of_bridges · intro n t exact enum_membership _ _ (Nat.lt_succ_self _) t · intro n exact enum_nodup enum_sound _ _ /-! ### Implementation helpers -/ /-- The table `[C_0, ..., C_n]` of Catalan numbers, each next entry by `C_{m+1} = Σ_i C_i * C_{m-i}`. -/ def catalanTableUpTo : Nat → List Nat | 0 => [1] | m + 1 => let prev := catalanTableUpTo m prev ++ [(prev.zipWith (· * ·) prev.reverse).sum] /-! ### Main algorithm (impl) -/ /-- Count of unique BSTs on `input` nodes by dynamic programming for the Catalan recurrence. -/ def countUniqueBSTs (input : Input) : Output := (catalanTableUpTo input).getD input 0 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countUniqueBSTs_correct (input : Input) (h : isValidInput input) : numTrees_spec input (countUniqueBSTs input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput 3 #guard isValidInput 1 #guard isValidInput 2 /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput 0) #guard !(isValidInput 20) #guard !(isValidInput 100) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard numTrees_check 3 5 #guard numTrees_check 1 1 #guard numTrees_check 2 2 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(numTrees_check 3 2) #guard !(numTrees_check 1 2) #guard !(numTrees_check 2 3) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countUniqueBSTs 3 == 5 #guard countUniqueBSTs 1 == 1 #guard countUniqueBSTs 2 == 2 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard numTrees_check 3 (countUniqueBSTs 3) #guard numTrees_check 1 (countUniqueBSTs 1) #guard numTrees_check 2 (countUniqueBSTs 2) end PUniqueBinarySearchTrees