63. Invert a binary tree
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
Input: invert .leafOutput: Tree.leafInput: 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.
1inductive Tree where
2 | leaf
3 | node (left : Tree) (value : Int) (right : Tree)
4 deriving Repr, DecidableEq
givenLoading editor…
Type
\to in the editor, or click: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