62. Maximum depth of a binary tree

EasyProgramFree10 points

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

  1. Input: maxDepth .leafOutput: 0
  2. Input: maxDepth (.node .leaf 1 .leaf)Output: 1
  3. Input: 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.

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