import Mathlib /-! # Recover Binary Search Tree You are given the root of a binary search tree (BST), where the values of exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. ## Constraints - The number of nodes in the tree is in the range [2, 1000]. - -2^31 <= Node.val <= 2^31 - 1 ## Provided examples - `root = [1, 3, null, null, 2]` → `[3, 1, null, null, 2]` - `root = [3, 1, 4, null, null, 2]` → `[2, 1, 4, null, null, 3]` - `root = [2, 3, 1]` → `[2, 1, 3]` ## Synthesized negative examples - invalid input: `root = []` ([structural] a predicate that admits The number of nodes in the tree is in the range [2, 1000].. empty tree below the minimum; a predicate tolerating null root passes it.) - invalid input: `root = [2147483648, 1]` ([structural] a predicate that admits -2^31 <= Node.val <= 2^31 - 1. one above the upper bound; a predicate checking only the lower bound accepts it.) - invalid input: `root = [5]` ([structural] a predicate that admits The number of nodes in the tree is in the range [2, 1000].. single node below the minimum; a predicate checking nonempty but not at least two passes it.) - `root = [1, 3, null, null, 2]` → `[1, 3, null, null, 2]` is wrong ([structural] no requirement forces the output to differ from the input or to be a BST. echoes input, satisfying a do-nothing recovery spec) - `root = [3, 1, 4, null, null, 2]` → `[2, 1, 5, null, null, 3]` is wrong ([structural] values need not match the original node values. same shape and BST, but 4 replaced by 5) - `root = [1, 3, null, null, 2]` → `[3, 1, null, null, 3]` is wrong ([structural] the result differs from the required one in at least one position. amended 2026-08-18: second mutation of a screened positive to reach quota) -/ namespace PRecoverBinarySearchTree abbrev Input := List (Option Int) abbrev Output := List (Option Int) /-! ### Specification helpers -/ /-- Converts the frozen level-order JSON form to the declared tree-list representation. -/ def treeListFromJson (entries : List (Option Int)) : List (Option Int) := entries /-- Collects the values present in a level-order serialization. -/ def nodeValues (serialization : List (Option Int)) : List Int := serialization.filterMap (fun entry => entry) /-- Counts the nodes present in a level-order serialization. -/ def nodeCount (serialization : List (Option Int)) : Nat := (nodeValues serialization).length /-- Checks that every present node in the suffix has a present parent. -/ def presentNodesHaveParentsFrom (serialization : List (Option Int)) (start : Nat) : List (Option Int) → Bool | [] => true | entry :: rest => (match entry with | none => true | some _ => start == 0 || match serialization[(start - 1) / 2]? with | some (some _) => true | _ => false) && presentNodesHaveParentsFrom serialization (start + 1) rest /-- Checks that a list is a canonical level-order serialization of a nonempty tree. -/ def isValidSerialization (serialization : List (Option Int)) : Bool := (match serialization[0]? with | some (some _) => true | _ => false) && (match serialization[serialization.length - 1]? with | some (some _) => true | _ => false) && presentNodesHaveParentsFrom serialization 0 serialization /-- Lists node values in in-order using the remaining traversal fuel. -/ def inorderValuesAux (serialization : List (Option Int)) : Nat → Nat → List Int | 0, _ => [] | fuel + 1, index => match serialization[index]? with | some (some value) => inorderValuesAux serialization fuel (2 * index + 1) ++ [value] ++ inorderValuesAux serialization fuel (2 * index + 2) | _ => [] /-- Lists the values of a level-order tree in in-order. -/ def inorderValues (serialization : List (Option Int)) : List Int := inorderValuesAux serialization serialization.length 0 /-- Inserts an integer into a nondecreasingly sorted list. -/ def insertSorted (value : Int) : List Int → List Int | [] => [value] | head :: tail => if value ≤ head then value :: head :: tail else head :: insertSorted value tail /-- Sorts a list of integers into nondecreasing order. -/ def sortValues : List Int → List Int | [] => [] | head :: tail => insertSorted head (sortValues tail) /-- Checks whether a list of integers is strictly increasing. -/ def isStrictlySorted : List Int → Bool | [] => true | [_] => true | first :: second :: rest => decide (first < second) && isStrictlySorted (second :: rest) /-- Finds the positions at which two integer lists have different entries. -/ def mismatchIndicesFrom : List Int → List Int → Nat → List Nat | value :: values, sortedValue :: sortedValues, index => (if value = sortedValue then [] else [index]) ++ mismatchIndicesFrom values sortedValues (index + 1) | _, _, _ => [] /-- Checks whether interchanging exactly two entries makes a list strictly sorted. -/ def isOneSwapFromStrictlySorted (values : List Int) : Bool := let sorted := sortValues values isStrictlySorted sorted && match mismatchIndicesFrom values sorted 0 with | [first, second] => (values[first]? == sorted[second]?) && (values[second]? == sorted[first]?) | _ => false /-- A list is a canonical level-order serialization of a nonempty binary tree. -/ def IsLevelOrderTree (serialization : List (Option Int)) : Prop := (∃ rootValue : Int, serialization[0]? = some (some rootValue)) ∧ (∃ lastValue : Int, serialization[serialization.length - 1]? = some (some lastValue)) ∧ ∀ index value, 0 < index → serialization[index]? = some (some value) → ∃ parentValue : Int, serialization[(index - 1) / 2]? = some (some parentValue) /-- Index `descendant` lies in the subtree rooted at index `root`. -/ inductive IsInSubtree : Nat → Nat → Prop where | refl (root : Nat) : IsInSubtree root root | left {root descendant : Nat} : IsInSubtree (2 * root + 1) descendant → IsInSubtree root descendant | right {root descendant : Nat} : IsInSubtree (2 * root + 2) descendant → IsInSubtree root descendant /-- Every left-subtree value is smaller and every right-subtree value is larger. -/ def HasBSTValues (serialization : List (Option Int)) : Prop := ∀ nodeIndex nodeValue, serialization[nodeIndex]? = some (some nodeValue) → (∀ descendantIndex descendantValue, IsInSubtree (2 * nodeIndex + 1) descendantIndex → serialization[descendantIndex]? = some (some descendantValue) → descendantValue < nodeValue) ∧ (∀ descendantIndex descendantValue, IsInSubtree (2 * nodeIndex + 2) descendantIndex → serialization[descendantIndex]? = some (some descendantValue) → nodeValue < descendantValue) /-- A level-order serialization represents a binary search tree. -/ def IsValidBST (serialization : List (Option Int)) : Prop := IsLevelOrderTree serialization ∧ HasBSTValues serialization /-- Two serializations have the same tree shape and the same node values. -/ def SameShapeAndValues (first second : List (Option Int)) : Prop := first.map Option.isSome = second.map Option.isSome ∧ List.Perm (nodeValues first) (nodeValues second) /-! ### Validity predicate (V) -/ /-- Valid input: a two-to-1000-node Int32-valued serialization obtainable from a BST by one interchange. -/ def isValidInput (input : Input) : Bool := isValidSerialization input && decide (2 ≤ nodeCount input ∧ nodeCount input ≤ 1000) && (nodeValues input).all (fun value => decide ((-2147483648 : Int) ≤ value ∧ value ≤ (2147483647 : Int))) && isOneSwapFromStrictlySorted (inorderValues input) /-! ### Ideal specification (P_spec) -/ /-- `result` has the input's shape and values and represents a binary search tree. -/ def recoverTree_spec (input : Input) (result : Output) : Prop := SameShapeAndValues input result ∧ IsValidBST result /-! ### Decidable specification (P_check) -/ /-- Executable checker for `recoverTree_spec`: same shape and values, and the recovered serialization is a valid binary search tree. -/ def recoverTree_check (input : Input) (result : Output) : Bool := (decide (input.map Option.isSome = result.map Option.isSome) && decide (sortValues (nodeValues input) = sortValues (nodeValues result))) && (isValidSerialization result && isStrictlySorted (inorderValues result)) theorem root_of_bridges (sort_bridge : ∀ a b : List Int, sortValues a = sortValues b ↔ a.Perm b) (serialization_bridge : ∀ s, isValidSerialization s = true ↔ IsLevelOrderTree s) (bst_bridge : ∀ s, IsLevelOrderTree s → (isStrictlySorted (inorderValues s) = true ↔ HasBSTValues s)) (input : Input) (result : Output) : recoverTree_check input result ↔ recoverTree_spec input result := by simp only [recoverTree_check, recoverTree_spec, SameShapeAndValues, IsValidBST, Bool.and_eq_true, decide_eq_true_eq, sort_bridge, serialization_bridge] constructor · rintro ⟨a, b, c⟩ exact ⟨a, b, (bst_bridge result b).mp c⟩ · rintro ⟨a, b, c⟩ exact ⟨a, b, (bst_bridge result b).mpr c⟩ lemma subtree_le {i j : Nat} (h : IsInSubtree i j) : i ≤ j := by induction h with | refl => omega | left h ih => omega | right h ih => omega lemma subtree_present (s : List (Option Int)) (hs : IsLevelOrderTree s) {i j : Nat} (h : IsInSubtree i j) {v : Int} (hv : s[j]? = some (some v)) : ∃ w, s[i]? = some (some w) := by induction h with | refl => exact ⟨v, hv⟩ | @left i j h ih => obtain ⟨w, hw⟩ := ih hv have hh := hs.2.2 (2*i+1) w (by omega) hw have he : (2*i+1-1)/2 = i := by omega simpa only [he] using hh | @right i j h ih => obtain ⟨w, hw⟩ := ih hv have hh := hs.2.2 (2*i+2) w (by omega) hw have he : (2*i+2-1)/2 = i := by omega simpa only [he] using hh lemma inorder_mem (s : List (Option Int)) (hs : IsLevelOrderTree s) (f i : Nat) (hb : s.length ≤ i + f) (v : Int) : v ∈ inorderValuesAux s f i ↔ ∃ j, IsInSubtree i j ∧ s[j]? = some (some v) := by induction f generalizing i with | zero => simp only [inorderValuesAux, List.not_mem_nil, false_iff, not_exists, not_and] intro j hj hv have hjb : j < s.length := List.getElem?_eq_some_iff.mp hv |>.1 have := subtree_le hj omega | succ f ih => cases he : s[i]? with | none => simp only [inorderValuesAux, he, List.not_mem_nil, false_iff, not_exists, not_and] intro j hj hv obtain ⟨w, hw⟩ := subtree_present s hs hj hv simp [he] at hw | some o => cases o with | none => simp only [inorderValuesAux, he, List.not_mem_nil, false_iff, not_exists, not_and] intro j hj hv obtain ⟨w, hw⟩ := subtree_present s hs hj hv simp [he] at hw | some w => simp only [inorderValuesAux, he, List.mem_append, List.mem_singleton] rw [ih (2*i+1) (by omega), ih (2*i+2) (by omega)] constructor · rintro ((⟨j,hj,hv⟩ | rfl) | ⟨j,hj,hv⟩) · exact ⟨j, IsInSubtree.left hj, hv⟩ · exact ⟨i, IsInSubtree.refl i, he⟩ · exact ⟨j, IsInSubtree.right hj, hv⟩ · rintro ⟨j,hj,hv⟩ cases hj with | refl => simp_all | left hj => exact Or.inl (Or.inl ⟨j,hj,hv⟩) | right hj => exact Or.inr ⟨j,hj,hv⟩ lemma pairwise_node (l r : List Int) (v : Int) : (l ++ [v] ++ r).Pairwise (· < ·) ↔ l.Pairwise (· < ·) ∧ r.Pairwise (· < ·) ∧ (∀ a ∈ l, a < v) ∧ (∀ b ∈ r, v < b) := by simp only [List.append_assoc, List.singleton_append, List.pairwise_append, List.pairwise_cons, List.mem_cons] constructor · rintro ⟨hl, ⟨hrv, hr⟩, hcross⟩ exact ⟨hl, hr, fun a ha => hcross a ha v (Or.inl rfl), hrv⟩ · rintro ⟨hl, hr, hlv, hrv⟩ refine ⟨hl, ⟨hrv, hr⟩, ?_⟩ intro a ha b hb rcases hb with rfl | hb · exact hlv a ha · exact lt_trans (hlv a ha) (hrv b hb) lemma bst_sorted_aux (s : List (Option Int)) (hs : IsLevelOrderTree s) (ht : HasBSTValues s) (f i : Nat) (hb : s.length ≤ i + f) : (inorderValuesAux s f i).Pairwise (· < ·) := by induction f generalizing i with | zero => simp [inorderValuesAux] | succ f ih => cases he : s[i]? with | none => simp [inorderValuesAux, he] | some o => cases o with | none => simp [inorderValuesAux, he] | some v => simp only [inorderValuesAux, he, pairwise_node] refine ⟨ih _ (by omega), ih _ (by omega), ?_, ?_⟩ · intro a ha obtain ⟨j, hj, hv⟩ := (inorder_mem s hs f (2*i+1) (by omega) a).mp ha exact (ht i v he).1 j a hj hv · intro a ha obtain ⟨j, hj, hv⟩ := (inorder_mem s hs f (2*i+2) (by omega) a).mp ha exact (ht i v he).2 j a hj hv lemma sorted_bst_aux (s : List (Option Int)) (hs : IsLevelOrderTree s) (f i : Nat) (hb : s.length ≤ i + f) (ht : (inorderValuesAux s f i).Pairwise (· < ·)) : ∀ j v, IsInSubtree i j → s[j]? = some (some v) → (∀ d w, IsInSubtree (2*j+1) d → s[d]? = some (some w) → w < v) ∧ (∀ d w, IsInSubtree (2*j+2) d → s[d]? = some (some w) → v < w) := by induction f generalizing i with | zero => intro j v hj hv have hjb : j < s.length := List.getElem?_eq_some_iff.mp hv |>.1 have := subtree_le hj omega | succ f ih => intro j v hj hv obtain ⟨w, hw⟩ := subtree_present s hs hj hv simp only [inorderValuesAux, hw, pairwise_node] at ht cases hj with | refl => have he : w = v := by simpa [hw] using hv subst w constructor · intro d z hd hz exact ht.2.2.1 z ((inorder_mem s hs f (2*i+1) (by omega) z).mpr ⟨d,hd,hz⟩) · intro d z hd hz exact ht.2.2.2 z ((inorder_mem s hs f (2*i+2) (by omega) z).mpr ⟨d,hd,hz⟩) | left hj => exact ih (2*i+1) (by omega) ht.1 j v hj hv | right hj => exact ih (2*i+2) (by omega) ht.2.1 j v hj hv lemma subtree_trans {i j k : Nat} (h : IsInSubtree i j) (g : IsInSubtree j k) : IsInSubtree i k := by induction h with | refl => exact g | left h ih => exact IsInSubtree.left (ih g) | right h ih => exact IsInSubtree.right (ih g) lemma subtree_zero (j : Nat) : IsInSubtree 0 j := by induction j using Nat.strong_induction_on with | h j ih => by_cases hz : j = 0 · subst j; exact IsInSubtree.refl 0 · have hp : (j-1)/2 < j := by omega have hh := ih ((j-1)/2) hp have hc : j = 2*((j-1)/2)+1 ∨ j = 2*((j-1)/2)+2 := by omega apply subtree_trans hh rcases hc with hc | hc · simpa only [← hc] using (IsInSubtree.left (root := (j-1)/2) (IsInSubtree.refl (2*((j-1)/2)+1))) · simpa only [← hc] using (IsInSubtree.right (root := (j-1)/2) (IsInSubtree.refl (2*((j-1)/2)+2))) lemma strictly_pairwise (xs : List Int) : isStrictlySorted xs = true ↔ xs.Pairwise (· < ·) := by rw [← List.sortedLT_iff_pairwise, List.sortedLT_iff_isChain] induction xs with | nil => simp [isStrictlySorted] | cons a xs ih => cases xs with | nil => simp [isStrictlySorted] | cons b xs => simpa only [isStrictlySorted, Bool.and_eq_true, decide_eq_true_eq, List.isChain_cons_cons] using and_congr Iff.rfl ih lemma bst_bridge (s : List (Option Int)) (hs : IsLevelOrderTree s) : isStrictlySorted (inorderValues s) = true ↔ HasBSTValues s := by rw [strictly_pairwise] constructor · intro ht j v hv exact sorted_bst_aux s hs s.length 0 (by omega) ht j v (subtree_zero j) hv · intro ht exact bst_sorted_aux s hs ht s.length 0 (by omega) theorem insertSorted_eq_orderedInsert (x : Int) : ∀ l : List Int, insertSorted x l = l.orderedInsert (· ≤ ·) x := by intro l induction l with | nil => rfl | cons y ys ih => simp only [insertSorted, List.orderedInsert_cons] split <;> simp_all theorem sortValues_eq_insertionSort : ∀ l : List Int, sortValues l = l.insertionSort (· ≤ ·) := by intro l induction l with | nil => rfl | cons x xs ih => simp only [sortValues, List.insertionSort_cons, ih, insertSorted_eq_orderedInsert] theorem sort_bridge : ∀ a b : List Int, sortValues a = sortValues b ↔ a.Perm b := by intro a b simp only [sortValues_eq_insertionSort] constructor · intro h exact (List.perm_insertionSort (· ≤ ·) a).symm |>.trans (h ▸ List.perm_insertionSort (· ≤ ·) b) · intro h apply List.Perm.eq_of_sortedLE (List.sortedLE_insertionSort) (List.sortedLE_insertionSort) exact (List.perm_insertionSort (· ≤ ·) a).trans (h.trans (List.perm_insertionSort (· ≤ ·) b).symm) theorem nestedOptionMatch_true_iff (entry : Option (Option Int)) : (match entry with | some (some _) => true | _ => false) = true ↔ ∃ value : Int, entry = some (some value) := by cases entry with | none => simp | some entry => cases entry <;> simp theorem presentNodesHaveParentsFrom_bridge (serialization : List (Option Int)) : ∀ (suffix : List (Option Int)) (start : Nat), presentNodesHaveParentsFrom serialization start suffix = true ↔ ∀ index value, suffix[index]? = some (some value) → start + index = 0 ∨ ∃ parentValue : Int, serialization[(start + index - 1) / 2]? = some (some parentValue) := by intro suffix induction suffix with | nil => intro start simp [presentNodesHaveParentsFrom] | cons entry rest ih => intro start rw [presentNodesHaveParentsFrom.eq_def, Bool.and_eq_true, ih] constructor · rintro ⟨hentry, hrest⟩ index value hvalue cases index with | zero => simp only [List.getElem?_cons_zero] at hvalue cases entry with | none => simp at hvalue | some entryValue => simp only [Option.some.injEq] at hvalue subst entryValue simpa [nestedOptionMatch_true_iff] using hentry | succ index => simp only [List.getElem?_cons_succ] at hvalue have hp := hrest index value hvalue simpa [Nat.add_assoc, Nat.add_comm, Nat.add_left_comm] using hp · intro h constructor · cases entry with | none => simp | some entryValue => simpa [nestedOptionMatch_true_iff] using h 0 entryValue rfl · intro index value hvalue have hp := h (index + 1) value (by simpa using hvalue) simpa [Nat.add_assoc, Nat.add_comm, Nat.add_left_comm] using hp theorem serialization_bridge : ∀ serialization : List (Option Int), isValidSerialization serialization = true ↔ IsLevelOrderTree serialization := by intro serialization rw [isValidSerialization, Bool.and_eq_true, Bool.and_eq_true, presentNodesHaveParentsFrom_bridge] simp only [IsLevelOrderTree] constructor · rintro ⟨⟨hroot, hlast⟩, hparents⟩ constructor · exact (nestedOptionMatch_true_iff _).mp hroot constructor · exact (nestedOptionMatch_true_iff _).mp hlast · intro index value hpos hvalue rcases hparents index value hvalue with hzero | hparent · omega · simpa using hparent · rintro ⟨hroot, hlast, hparents⟩ constructor · exact ⟨(nestedOptionMatch_true_iff _).mpr hroot, (nestedOptionMatch_true_iff _).mpr hlast⟩ · intro index value hvalue by_cases hzero : index = 0 · exact Or.inl (by omega) · exact Or.inr (by simpa using hparents index value (by omega) hvalue) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem recoverTree_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : recoverTree_check input result ↔ recoverTree_spec input result := by exact root_of_bridges sort_bridge serialization_bridge bst_bridge input result /-! ### Implementation helpers -/ /-- Lists level-order indices in in-order using the remaining traversal fuel. -/ def inorderIndicesAux (serialization : List (Option Int)) : Nat → Nat → List Nat | 0, _ => [] | fuel + 1, index => match serialization[index]? with | some (some _) => inorderIndicesAux serialization fuel (2 * index + 1) ++ [index] ++ inorderIndicesAux serialization fuel (2 * index + 2) | _ => [] /-- Lists the level-order indices of a tree in in-order. -/ def inorderIndices (serialization : List (Option Int)) : List Nat := inorderIndicesAux serialization serialization.length 0 /-- Scans in-order (value, index) pairs, tracking the previous pair, to locate the two out-of-order positions. -/ def findSwappedIndicesAux : List (Int × Nat) → Int → Nat → Option (Nat × Nat) → Nat × Nat | [], _, _, found => found.getD (0, 0) | (value, index) :: rest, prevValue, prevIndex, found => if value < prevValue then match found with | none => findSwappedIndicesAux rest value index (some (prevIndex, index)) | some (firstIndex, _) => findSwappedIndicesAux rest value index (some (firstIndex, index)) else findSwappedIndicesAux rest value index found /-- Finds the level-order indices of the two nodes whose values were interchanged. -/ def findSwappedIndices (serialization : List (Option Int)) : Nat × Nat := match (inorderValues serialization).zip (inorderIndices serialization) with | [] => (0, 0) | (value, index) :: rest => findSwappedIndicesAux rest value index none /-- Exchanges the entries at positions `first` and `second` of a level-order list. -/ def swapValuesAt (first second : Nat) (entries : List (Option Int)) : List (Option Int) := walk ((entries[first]?).getD none) ((entries[second]?).getD none) 0 entries where walk (firstValue secondValue : Option Int) (index : Nat) : List (Option Int) → List (Option Int) | [] => [] | entry :: rest => (if index = first then secondValue else if index = second then firstValue else entry) :: walk firstValue secondValue (index + 1) rest /-! ### Main algorithm (impl) -/ /-- Lists the level-order indices of the present nodes in in-order. The recursion is well-founded rather than fuel-bounded: each recursive call moves to a strictly larger child index (`2 * index + 1` or `2 * index + 2`) while the list stays fixed, so the measure `serialization.length - index` strictly decreases through `termination_by`. Every present node occupies an index below the list length, so the traversal visits exactly the present nodes and skips nothing. -/ def inorderPositions (serialization : List (Option Int)) (index : Nat) : List Nat := if h : index < serialization.length then match serialization[index] with | some _ => inorderPositions serialization (2 * index + 1) ++ [index] ++ inorderPositions serialization (2 * index + 2) | none => [] else [] termination_by serialization.length - index decreasing_by all_goals omega /-- Recovers the tree by finding the two values out of in-order order and swapping them back. -/ def recoverSwappedBST (input : Input) : Output := let indices := inorderPositions input 0 let pairs := indices.filterMap fun i => match input[i]? with | some (some value) => some (value, i) | _ => none match pairs with | [] => input | (value, firstIndex) :: rest => let (first, second) := findSwappedIndicesAux rest value firstIndex none swapValuesAt first second input /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem recoverSwappedBST_correct (input : Input) (h : isValidInput input) : recoverTree_spec input (recoverSwappedBST input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (treeListFromJson [(some 1), (some 3), none, none, (some 2)]) #guard isValidInput (treeListFromJson [(some 3), (some 1), (some 4), none, none, (some 2)]) #guard isValidInput (treeListFromJson [(some 2), (some 3), (some 1)]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (treeListFromJson [])) #guard !(isValidInput (treeListFromJson [(some 2147483648), (some 1)])) #guard !(isValidInput (treeListFromJson [(some 5)])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard recoverTree_check (treeListFromJson [(some 1), (some 3), none, none, (some 2)]) [(some 3), (some 1), none, none, (some 2)] #guard recoverTree_check (treeListFromJson [(some 3), (some 1), (some 4), none, none, (some 2)]) [(some 2), (some 1), (some 4), none, none, (some 3)] #guard recoverTree_check (treeListFromJson [(some 2), (some 3), (some 1)]) [(some 2), (some 1), (some 3)] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(recoverTree_check (treeListFromJson [(some 1), (some 3), none, none, (some 2)]) [(some 1), (some 3), none, none, (some 2)]) #guard !(recoverTree_check (treeListFromJson [(some 3), (some 1), (some 4), none, none, (some 2)]) [(some 2), (some 1), (some 5), none, none, (some 3)]) #guard !(recoverTree_check (treeListFromJson [(some 1), (some 3), none, none, (some 2)]) [(some 3), (some 1), none, none, (some 3)]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard recoverSwappedBST (treeListFromJson [(some 1), (some 3), none, none, (some 2)]) == [(some 3), (some 1), none, none, (some 2)] #guard recoverSwappedBST (treeListFromJson [(some 3), (some 1), (some 4), none, none, (some 2)]) == [(some 2), (some 1), (some 4), none, none, (some 3)] #guard recoverSwappedBST (treeListFromJson [(some 2), (some 3), (some 1)]) == [(some 2), (some 1), (some 3)] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard recoverTree_check (treeListFromJson [(some 1), (some 3), none, none, (some 2)]) (recoverSwappedBST (treeListFromJson [(some 1), (some 3), none, none, (some 2)])) #guard recoverTree_check (treeListFromJson [(some 3), (some 1), (some 4), none, none, (some 2)]) (recoverSwappedBST (treeListFromJson [(some 3), (some 1), (some 4), none, none, (some 2)])) #guard recoverTree_check (treeListFromJson [(some 2), (some 3), (some 1)]) (recoverSwappedBST (treeListFromJson [(some 2), (some 3), (some 1)])) end PRecoverBinarySearchTree