62. Maximum depth of a binary tree
A Tree is either empty, .leaf, or a .node left value right. Write maxDepth t, the number of nodes on the longest path from the root of t down to an empty subtree.
The empty tree has depth 0 and a single node has depth 1. In the third example, written [3, 9, 20, null, null, 15, 7] elsewhere, the longest path is 3 → 20 → 15.
Examples
Input: maxDepth .leafOutput: 0Input: maxDepth (.node .leaf 1 .leaf)Output: 1Input: maxDepth (.node (.node .leaf 9 .leaf) 3 (.node (.node .leaf 15 .leaf) 20 (.node .leaf 7 .leaf)))Output: 3
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