import Mathlib /-! # Binary Tree Inorder Traversal Given the root of a binary tree, return the inorder traversal of its nodes' values. ## Constraints - The number of nodes in the tree is in the range [0, 100]. - -100 <= Node.val <= 100 ## Provided examples - `root = [1, null, 2, 3]` → `[1, 3, 2]` - `root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]` → `[4, 2, 6, 5, 7, 1, 3, 9, 8]` - `root = []` → `[]` ## Synthesized negative examples - invalid input: `root = [101]` ([structural] a predicate that admits -100 <= Node.val <= 100. one above the upper value bound; catches a lower-bound-only predicate) - invalid input: `root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 1]` ([structural] a predicate that admits The number of nodes in the tree is in the range [0, 100].. one node above the maximum size; catches a predicate that omits the length cap) - invalid input: `root = [-101]` ([structural] a predicate that admits -100 <= Node.val <= 100. one below the lower value bound; catches an upper-bound-only predicate) - `root = [1, null, 2, 3]` → `[1, 2, 3]` is wrong ([structural] traversal stated without the inorder condition. valid preorder, so only the order is wrong) - `root = [1, 2, 3, 4, 5, null, 8, null, null, 6, 7, 9]` → `[4, 2, 6, 5, 7, 1, 3, 9, 8, 3]` is wrong ([structural] cardinality omitted: extra elements are not forbidden. appends an extra 3; length exceeds node count) - `root = []` → `[-1]` is wrong ([structural] the traversal may append a sentinel element. one extra element beyond the node count) -/ namespace PBinaryTreeInorderTraversal /-! ### Representation -/ /-- Binary tree with integer-valued nodes, mirroring the source TreeNode. -/ inductive BinTree where | empty : BinTree | node (val : Int) (left right : BinTree) : BinTree deriving BEq /-- A bare numeric literal at `Option Int` denotes `some` of that literal. -/ instance instOfNatOptionInt (n : Nat) : OfNat (Option Int) n := ⟨some (n : Int)⟩ /-- Negation at `Option Int` negates the carried value and preserves `none`. -/ instance instNegOptionInt : Neg (Option Int) := ⟨Option.map Neg.neg⟩ abbrev Input := BinTree abbrev Output := List Int /-! ### Specification helpers -/ /-- Attach the next-level trees in `ts` as children of the nodes described by `vs`, in order. -/ def attachChildren : List (Option Int) → List BinTree → List BinTree | [], _ => [] | none :: vs, ts => BinTree.empty :: attachChildren vs ts | some v :: vs, t1 :: t2 :: ts => BinTree.node v t1 t2 :: attachChildren vs ts | some v :: vs, [t] => BinTree.node v t BinTree.empty :: attachChildren vs [] | some v :: vs, [] => BinTree.node v BinTree.empty BinTree.empty :: attachChildren vs [] /-- Build the forest whose `slots` next entries of `l` are its level-order values, returning the trees and the unread suffix; `fuel` bounds the number of levels. -/ def fillLevel : Nat → Nat → List (Option Int) → List BinTree × List (Option Int) | 0, _, l => ([], l) | fuel + 1, slots, l => if slots = 0 then ([], l) else let (levelVals, rest) := l.splitAt slots let (childTrees, rest') := fillLevel fuel (2 * (levelVals.filter Option.isSome).length) rest (attachChildren levelVals childTrees, rest') /-- Deserialize a LeetCode level-order array of values and nulls into a `BinTree`. -/ def arrayToTree (l : List (Option Int)) : BinTree := match l with | [] => BinTree.empty | none :: _ => BinTree.empty | some v :: rest => match (fillLevel l.length 2 rest).1 with | t1 :: t2 :: _ => BinTree.node v t1 t2 | [t] => BinTree.node v t BinTree.empty | [] => BinTree.node v BinTree.empty BinTree.empty /-- The number of nodes in a `BinTree`. -/ def TreeSize : BinTree → Nat | BinTree.empty => 0 | BinTree.node _ l r => TreeSize l + 1 + TreeSize r /-- `x` is the value stored at the node visited at position `n` of the inorder traversal of the tree. -/ inductive IsInorderAt : BinTree → Nat → Int → Prop where | left {v : Int} {l r : BinTree} {n : Nat} {x : Int} : n < TreeSize l → IsInorderAt l n x → IsInorderAt (BinTree.node v l r) n x | here {v : Int} {l r : BinTree} : IsInorderAt (BinTree.node v l r) (TreeSize l) v | right {v : Int} {l r : BinTree} {j : Nat} {x : Int} : IsInorderAt r j x → IsInorderAt (BinTree.node v l r) (TreeSize l + 1 + j) x /-- Every value stored in a node of the tree lies between -100 and 100 inclusive. -/ def nodeValuesInRange : BinTree → Bool | BinTree.empty => true | BinTree.node v l r => (-100 ≤ v && v ≤ 100) && nodeValuesInRange l && nodeValuesInRange r /-! ### Validity predicate (V) -/ /-- Valid input: a tree of at most 100 nodes whose every value lies between -100 and 100 inclusive. -/ def isValidInput (input : Input) : Bool := TreeSize input ≤ 100 && nodeValuesInRange input /-! ### Ideal specification (P_spec) -/ /-- `result` has one entry per node of `input`, and the entry at each position is the value the inorder traversal visits there. -/ def inorderTraversal_spec (input : Input) (result : Output) : Prop := result.length = TreeSize input ∧ ∀ (i : Nat) (h : i < result.length), IsInorderAt input i (result.get ⟨i, h⟩) /-! ### Decidable specification (P_check) -/ /-- Decides `IsInorderAt t n x`, the body of the specification's bounded quantifier, by structural recursion on the tree: comparing `n` with the size of the left subtree determines whether inorder position `n` lies in the left subtree, at the root, or in the right subtree, and each case is either a decidable equality or a recursive call on a strictly smaller tree. -/ instance decIsInorderAt : (t : BinTree) → (n : Nat) → (x : Int) → Decidable (IsInorderAt t n x) | BinTree.empty, _, _ => isFalse (fun h => by cases h) | BinTree.node v l r, n, x => if hlt : n < TreeSize l then match decIsInorderAt l n x with | isTrue h => isTrue (IsInorderAt.left hlt h) | isFalse h => isFalse (fun hh => by cases hh with | left _ h' => exact h h' | here => omega | right _ => omega) else if heq : n = TreeSize l then if hxv : x = v then isTrue (by subst heq; subst hxv; exact IsInorderAt.here) else isFalse (fun hh => by cases hh with | left h' _ => exact hlt h' | here => exact hxv rfl | right _ => omega) else match decIsInorderAt r (n - (TreeSize l + 1)) x with | isTrue h => isTrue (by have hn : n = TreeSize l + 1 + (n - (TreeSize l + 1)) := by omega rw [hn] exact IsInorderAt.right h) | isFalse h => isFalse (fun hh => by cases hh with | left h' _ => exact hlt h' | here => exact heq rfl | right h' => exact h (by rw [Nat.add_sub_cancel_left]; exact h')) /-- Decides the full unfolded specification: the length equation is decidable equality on `Nat`, and the universal quantifier ranges only over positions below `result.length`, so it is decided component by component once `IsInorderAt` is decidable. -/ instance decInorderTraversalSpec (input : Input) (result : Output) : Decidable (result.length = TreeSize input ∧ ∀ (i : Nat) (h : i < result.length), IsInorderAt input i (result.get ⟨i, h⟩)) := inferInstanceAs (Decidable (result.length = TreeSize input ∧ ∀ (i : Nat) (h : i < result.length), IsInorderAt input i (result.get ⟨i, h⟩))) /-- Executable checker obtained mechanically from the specification. -/ def inorderTraversal_check (input : Input) (result : Output) : Bool := @decide (inorderTraversal_spec input result) (by unfold inorderTraversal_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem inorderTraversal_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : inorderTraversal_check input result ↔ inorderTraversal_spec input result := by simp [inorderTraversal_check] /-! ### Implementation helpers -/ /-- Inorder traversal of `t` followed by the accumulator `acc`, built with cons only. -/ def go : BinTree → List Int → List Int | BinTree.empty, acc => acc | BinTree.node v l r, acc => go l (v :: go r acc) /-! ### Main algorithm (impl) -/ /-- Inorder traversal by accumulator-based structural recursion, left subtree, then value, then right subtree, in linear time. -/ def getInorderTraversal (input : Input) : Output := go input [] /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem getInorderTraversal_correct (input : Input) (h : isValidInput input) : inorderTraversal_spec input (getInorderTraversal input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (arrayToTree [(some 1), none, (some 2), (some 3)]) #guard isValidInput (arrayToTree [(some 1), (some 2), (some 3), (some 4), (some 5), none, (some 8), none, none, (some 6), (some 7), (some 9)]) #guard isValidInput (arrayToTree []) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (arrayToTree [101])) #guard !(isValidInput (arrayToTree [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, 100, 1])) #guard !(isValidInput (arrayToTree [(-101)])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard inorderTraversal_check (arrayToTree [(some 1), none, (some 2), (some 3)]) [1, 3, 2] #guard inorderTraversal_check (arrayToTree [(some 1), (some 2), (some 3), (some 4), (some 5), none, (some 8), none, none, (some 6), (some 7), (some 9)]) [4, 2, 6, 5, 7, 1, 3, 9, 8] #guard inorderTraversal_check (arrayToTree []) [] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(inorderTraversal_check (arrayToTree [(some 1), none, (some 2), (some 3)]) [1, 2, 3]) #guard !(inorderTraversal_check (arrayToTree [(some 1), (some 2), (some 3), (some 4), (some 5), none, (some 8), none, none, (some 6), (some 7), (some 9)]) [4, 2, 6, 5, 7, 1, 3, 9, 8, 3]) #guard !(inorderTraversal_check (arrayToTree []) [(-1)]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard getInorderTraversal (arrayToTree [(some 1), none, (some 2), (some 3)]) == [1, 3, 2] #guard getInorderTraversal (arrayToTree [(some 1), (some 2), (some 3), (some 4), (some 5), none, (some 8), none, none, (some 6), (some 7), (some 9)]) == [4, 2, 6, 5, 7, 1, 3, 9, 8] #guard getInorderTraversal (arrayToTree []) == [] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard inorderTraversal_check (arrayToTree [(some 1), none, (some 2), (some 3)]) (getInorderTraversal (arrayToTree [(some 1), none, (some 2), (some 3)])) #guard inorderTraversal_check (arrayToTree [(some 1), (some 2), (some 3), (some 4), (some 5), none, (some 8), none, none, (some 6), (some 7), (some 9)]) (getInorderTraversal (arrayToTree [(some 1), (some 2), (some 3), (some 4), (some 5), none, (some 8), none, none, (some 6), (some 7), (some 9)])) #guard inorderTraversal_check (arrayToTree []) (getInorderTraversal (arrayToTree [])) end PBinaryTreeInorderTraversal