import Mathlib /-! # Print Binary Tree Given the root of a binary tree, construct a 0-indexed m x n string matrix res that represents a formatted layout of the tree. The formatted layout matrix should be constructed using the following rules: The height of the tree is height and the number of rows m should be equal to height + 1. The number of columns n should be equal to 2^(height + 1) - 1. Place the root node in the middle of the top row (more formally, at location res[0][(n-1)/2]). For each node that has been placed in the matrix at position res[r][c], place its left child at res[r+1][c-2^(height - r - 1)] and its right child at res[r+1][c+2^(height - r - 1)]. Continue this process until all the nodes in the tree have been placed. Any empty cells should contain the empty string "". Return the constructed matrix res. ## Constraints - The number of nodes in the tree is in the range [1, 2^10]. - -99 <= Node.val <= 99 - The depth of the tree will be in the range [1, 10]. ## Provided examples - `root = [1, 2]` → `[["", "1", ""], ["2", "", ""]]` - `root = [1, 2, 3, null, 4]` → `[["", "", "", "1", "", "", ""], ["", "2", "", "", "", "3", ""], ["", "", "4", "", "", "", ""]]` - `root = [1]` → `[["1"]]` ## Synthesized negative examples - invalid input: `root = []` ([structural] a predicate that admits The number of nodes in the tree is in the range [1, 2^10].. empty tree has fewer than one node) - invalid input: `root = [100]` ([structural] a predicate that admits -99 <= Node.val <= 99. one past the stated maximum) - invalid input: `root = [1, 100]` ([structural] a predicate that admits -99 <= Node.val <= 99. child value one past maximum; catches a root-only checker) - `root = [1, 2]` → `[["", "", "", "1", "", "", ""], ["", "2", "", "", "", "", ""], ["", "", "", "", "", "", ""]]` is wrong ([structural] height is interpreted as the number of levels rather than edges, adding one row and two columns. correct layout for a tree of height 2) - `root = [1, 2, 3, null, 4]` → `[["", "", "", "1", "", "", ""], ["", "2", "", "", "", "3", ""], ["", "", "4", "", "", "", ""], ["", "", "", "", "", "", ""]]` is wrong ([structural] row count need not be exactly height+1. an extra empty row is accepted if only at least height+1 rows are required) - `root = [1]` → `[["1", ""]]` is wrong ([structural] column count one greater than 2^(height+1)-1. extra empty column beside the root) -/ namespace PPrintBinaryTree /-! ### Representation -/ /-- A binary tree with integer node values, empty or a node with two subtrees. -/ inductive BinTree (α : Type) where | nil : BinTree α | node : α → BinTree α → BinTree α → BinTree α deriving Repr, BEq, DecidableEq abbrev Input := BinTree Int abbrev Output := List (List String) /-! ### Specification helpers -/ /-- Number of nodes on a longest root-to-leaf path; `nil` has none. -/ def treeLevels : BinTree Int → Nat | .nil => 0 | .node _ l r => 1 + max (treeLevels l) (treeLevels r) /-- Number of edges on a longest root-to-leaf path; a single node has height 0. -/ def TreeHeight (t : BinTree Int) : Nat := treeLevels t - 1 /-- Number of nodes in the tree. -/ def nodeCount : BinTree Int → Nat | .nil => 0 | .node _ l r => 1 + nodeCount l + nodeCount r /-- Whether every node value lies in `[-99, 99]`. -/ def valuesInRange : BinTree Int → Bool | .nil => true | .node v l r => (-99 ≤ v && v ≤ 99) && valuesInRange l && valuesInRange r /-- Value of the node placed at absolute row `r`, column `c`, when the subtree root sits at column `col`, its root's row is `depth`, and the full tree has height `h`. -/ def placedValue (t : BinTree Int) (h depth : Nat) (col : Int) (r : Nat) (c : Int) : Option Int := match t with | .nil => none | .node v left right => if r = depth then if c = col then some v else none else if r < depth then none else let off : Int := (2 : Int) ^ (h - depth - 1) placedValue left h (depth + 1) (col - off) r c <|> placedValue right h (depth + 1) (col + off) r c /-- `s` is the required content of cell `(r, c)`: the decimal value of the node placed there, or the empty string when no node is placed there. -/ def ExpectedCell (t : BinTree Int) (r c : Nat) (s : String) : Prop := s = match placedValue t (TreeHeight t) 0 ((2 : Int) ^ TreeHeight t - 1) r (c : Int) with | some v => toString v | none => "" /-- Subtree rooted at array index `i` of a level-order serialization, with `fuel` levels left. -/ def arrayToBinTreeAux (l : List (Option Int)) : Nat → Nat → BinTree Int | 0, _ => .nil | fuel + 1, i => match l[i]? with | some (some v) => .node v (arrayToBinTreeAux l fuel (2 * i + 1)) (arrayToBinTreeAux l fuel (2 * i + 2)) | _ => .nil /-- Deserialize a level-order array of optional values into the corresponding tree. -/ def arrayToBinTree (l : List (Option Int)) : BinTree Int := arrayToBinTreeAux l l.length 0 /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 2^10 nodes, every value in `[-99, 99]`, and depth in `[1, 10]`. -/ def isValidInput (input : Input) : Bool := 1 ≤ nodeCount input && nodeCount input ≤ 2 ^ 10 && valuesInRange input && TreeHeight input + 1 ≤ 10 /-! ### Ideal specification (P_spec) -/ /-- `result` is the formatted layout of `input`: it has `TreeHeight input + 1` rows of width `2^(TreeHeight input + 1) - 1`, and every cell holds the expected content. -/ def printTree_spec (input : Input) (result : Output) : Prop := (result.length = TreeHeight input + 1 ∧ ∀ row ∈ result, row.length = 2 ^ (TreeHeight input + 1) - 1) ∧ ∀ r c : Nat, r < TreeHeight input + 1 → c < 2 ^ (TreeHeight input + 1) - 1 → ExpectedCell input r c ((result[r]!)[c]!) /-! ### Decidable specification (P_check) -/ /-- Decides each `ExpectedCell input r c s` leaf of the specification: it is a string equality between `s` and the content prescribed by `placedValue` for cell `(r, c)`, decidable by `String`'s `DecidableEq` instance. The bounded quantifiers above it (`Nat.decidableBallLT`, `List.decidableBAll`) then resolve on their own. -/ instance decExpectedCell (t : BinTree Int) (r c : Nat) (s : String) : Decidable (ExpectedCell t r c s) := inferInstanceAs (Decidable (s = match placedValue t (TreeHeight t) 0 ((2 : Int) ^ TreeHeight t - 1) r (c : Int) with | some v => toString v | none => "")) /-- Decides the cell-content quantifier of the specification. As written, `∀ r c, r < H → c < W → …` nests `∀ c` before the hypothesis `r < H`, so `Nat.decidableBallLT` cannot see the bound. The instance reduces it to the equivalent curried form `∀ r, r < H → ∀ c, c < W → …`, where each hypothesis sits directly under its variable and Lean's own bounded-quantifier instances finish the job, bottoming out at `decExpectedCell`. -/ instance decCellGrid (input : Input) (result : Output) : Decidable (∀ r c : Nat, r < TreeHeight input + 1 → c < 2 ^ (TreeHeight input + 1) - 1 → ExpectedCell input r c ((result[r]!)[c]!)) := decidable_of_iff (∀ r, r < TreeHeight input + 1 → ∀ c, c < 2 ^ (TreeHeight input + 1) - 1 → ExpectedCell input r c ((result[r]!)[c]!)) ⟨fun h r c hr hc => h r hr c hc, fun h r hr c hc => h r c hr hc⟩ /-- Executable checker obtained mechanically from the specification. -/ def printTree_check (input : Input) (result : Output) : Bool := @decide (printTree_spec input result) (by unfold printTree_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem printTree_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : printTree_check input result ↔ printTree_spec input result := by simp [printTree_check] /-! ### Implementation helpers -/ /-- Builds `h + 1` fixed-width rows of empty strings for height `h`. -/ def emptyGrid (h : Nat) : List (List.Vector String (2 ^ (h + 1) - 1)) := List.replicate (h + 1) (List.Vector.replicate (2 ^ (h + 1) - 1) "") /-- Places every node of `t` from absolute row `r` and column `c` into the grid. -/ def fillSubtree {w : Nat} (t : BinTree Int) (h r : Nat) (c : Int) (grid : List (List.Vector String w)) : List (List.Vector String w) := match t with | .nil => grid | .node v left right => let grid' := if hnonneg : 0 ≤ c then let cn := c.toNat if hlt : cn < w then match grid[r]? with | some row => grid.set r (List.Vector.set row ⟨cn, hlt⟩ (toString v)) | none => grid else grid else grid let off : Int := (2 : Int) ^ (h - r - 1) let gridL := fillSubtree left h (r + 1) (c - off) grid' fillSubtree right h (r + 1) (c + off) gridL /-- Converts each fixed-width row vector into the required list of strings. -/ def vectorRowsToOutput {w : Nat} (rows : List (List.Vector String w)) : Output := rows.map (fun row => row.val) /-! ### Main algorithm (impl) -/ /-- Formats the tree by computing its height, allocating the full grid, and placing nodes top-down. -/ def formatBinaryTree (input : Input) : Output := let h := TreeHeight input let rootCol : Int := (2 : Int) ^ h - 1 vectorRowsToOutput (fillSubtree input h 0 rootCol (emptyGrid h)) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem formatBinaryTree_correct (input : Input) (h : isValidInput input) : printTree_spec input (formatBinaryTree input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (arrayToBinTree [(some 1), (some 2)]) #guard isValidInput (arrayToBinTree [(some 1), (some 2), (some 3), none, (some 4)]) #guard isValidInput (arrayToBinTree [(some 1)]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (arrayToBinTree [])) #guard !(isValidInput (arrayToBinTree [(some 100)])) #guard !(isValidInput (arrayToBinTree [(some 1), (some 100)])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard printTree_check (arrayToBinTree [(some 1), (some 2)]) [["", "1", ""], ["2", "", ""]] #guard printTree_check (arrayToBinTree [(some 1), (some 2), (some 3), none, (some 4)]) [["", "", "", "1", "", "", ""], ["", "2", "", "", "", "3", ""], ["", "", "4", "", "", "", ""]] #guard printTree_check (arrayToBinTree [(some 1)]) [["1"]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(printTree_check (arrayToBinTree [(some 1), (some 2)]) [["", "", "", "1", "", "", ""], ["", "2", "", "", "", "", ""], ["", "", "", "", "", "", ""]]) #guard !(printTree_check (arrayToBinTree [(some 1), (some 2), (some 3), none, (some 4)]) [["", "", "", "1", "", "", ""], ["", "2", "", "", "", "3", ""], ["", "", "4", "", "", "", ""], ["", "", "", "", "", "", ""]]) #guard !(printTree_check (arrayToBinTree [(some 1)]) [["1", ""]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard formatBinaryTree (arrayToBinTree [(some 1), (some 2)]) == [["", "1", ""], ["2", "", ""]] #guard formatBinaryTree (arrayToBinTree [(some 1), (some 2), (some 3), none, (some 4)]) == [["", "", "", "1", "", "", ""], ["", "2", "", "", "", "3", ""], ["", "", "4", "", "", "", ""]] #guard formatBinaryTree (arrayToBinTree [(some 1)]) == [["1"]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard printTree_check (arrayToBinTree [(some 1), (some 2)]) (formatBinaryTree (arrayToBinTree [(some 1), (some 2)])) #guard printTree_check (arrayToBinTree [(some 1), (some 2), (some 3), none, (some 4)]) (formatBinaryTree (arrayToBinTree [(some 1), (some 2), (some 3), none, (some 4)])) #guard printTree_check (arrayToBinTree [(some 1)]) (formatBinaryTree (arrayToBinTree [(some 1)])) end PPrintBinaryTree