63. Invert a binary tree

EasyProgramFree10 points

Write invert t, the mirror image of the tree t: at every node, the left and right subtrees change places, all the way down.

Inputs use the short form .node .leaf 5 .leaf; outputs are shown the way Lean prints a tree, Tree.node (Tree.leaf) 5 (Tree.leaf). Both mean the same tree.

Examples

  1. Input: invert .leafOutput: Tree.leaf
  2. Input: invert (.node (.node .leaf 1 .leaf) 2 (.node .leaf 3 .leaf))Output: Tree.node (Tree.node (Tree.leaf) 3 (Tree.leaf)) 2 (Tree.node (Tree.leaf) 1 (Tree.leaf))

Submitting also runs 4 hidden tests.

Solution.lean
1inductive Tree where
2 | leaf
3 | node (left : Tree) (value : Int) (right : Tree)
4 deriving Repr, DecidableEq
given
Loading editor…

Run checks your code against the examples and your custom inputs and records nothing. Submit also runs the hidden tests, confirms the axioms your proof uses and records the result. Each uses one compiler check.

ReadyLn 1, Col 1Lean 4
Draft saved in this browser