type 'a btree =
| Empty
| Node of 'a * 'a btree * 'a btree;;
let max x y = if x > y then x else y
let depth t =
let rec dep m = function (* d records current level, m records max depth so far *)
| [] -> m
| (Empty,d)::tl -> dep (max m d) tl
| (Node (_,l,r),d)::tl -> dep (max m d) ((l,d+1)::(r,d+1)::tl)
in
dep 0 [(t,0)]
Basically, you need 3 things:
- a list (stack) to store nodes along the paths
- a indicator to record the current depth
- the current max depth so far
Whenever we face a problem that needs to remove the possible stackoverflow problem, we should think two things: tail-recursive and explicit stack.
For tail-recursive, you have to find a way to explicitly store the temporary data generated through each recursion step.
For explicit stack, remember the reason that recursion can work is because internally it uses a stack with a limited size. If we analyse the logic and make that stack explicit, we then don't need that internal stack any more.