(* Example of tail recursive version of tree depth calculation (essentially DFS). *) type 'a tree = | Leaf of 'a | Node of 'a * 'a tree * 'a tree let rec full_tree v = function | 0 -> Leaf v | n -> Node (v, full_tree v (n-1), full_tree v (n-1)) let rec make_full_tree v tree = function | 0 -> tree | n -> make_full_tree v (Node (v, tree, tree)) (n-1) let rec make_left_tree v tree = function | 0 -> tree | n -> make_left_tree v (Node (v, tree, Leaf v)) (n-1) (* # let t1 = make_full_tree 1 (Leaf 2) 1_000_000;; # let t2 = make_left_tree 1 (Leaf 2) 1_000_000;; *) let rec depth = function | Leaf x -> 0 | Node(_,left,right) -> 1 + (max (depth left) (depth right)) let depth' tree = let rec aux depth = function | [] -> depth | (d, Leaf _) :: t -> aux (max d depth) t | (d, Node (_,left,right)) :: t -> aux depth ((d+1, left) :: (d+1, right) :: t) in aux 0 [0, tree] (* # let t = make_left_tree 1 (Leaf 2) 1_000_000;; # depth t;; # depth' t;; *)