OCaml binary tree depth with no stack overflow

Question

I have the following implementation for a binary tree and a depth function to calculate its depth:

type 'a btree =
| Empty
| Node of 'a * 'a btree * 'a btree;;

let rec depth t = match t with
| Empty -> 0
| Node (_, t1, t2) -> 1 + Int.max (depth t1)  (depth t2)

The problem here is that "depth" is recursive and can cause a stack overflow when the tree is too big.

I read about tail recursion and how it can be optimised into a while loop by the compiler to remove the stack call.

How would you make this function tail recursive or make it use a while/for loop instead?

Transforming this into a tail-recursive or iterative algorithm would require using an explicit stack. Is this a real problem or just an exercise? Because in actual applications, you'd either make sure the tree is balanced so the recursion isn't too deep, or store the depth in the nodes when constructing them. — Fred Foo, Jan 17 '14 at 10:45
Thanks for the tip for real world applications. This was an exercise, though. — SpaceMonkey, Jan 17 '14 at 10:49
Possible dublicate: http://stackoverflow.com/questions/9323036/tail-recursive-function-to-find-depth-of-a-tree-in-ocaml — Kakadu, Jan 17 '14 at 11:25

Jackson Tale · Accepted Answer · 2014-01-17T15:50:14.373

3

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.

edited Jan 17 '14 at 15:50

answered Jan 17 '14 at 11:46

Jackson Tale

25,428
34
149
271

Hmm.. seems like it doesn't work: given: Node (10, Node (5, Empty, Empty), Node (15, Empty, Empty)) It returns 7 – SpaceMonkey Jan 17 '14 at 15:35
That's quite clever (for me at least) I will have to reread it a few times though to understand it. Thanks a lot ! – SpaceMonkey Jan 17 '14 at 15:57
Another hint is that ocaml/FP is very convenient to combine info together, on temp basis. like I did, record the level info `d` with each node. – Jackson Tale Jan 17 '14 at 15:59
@Jackson_Tale so basically the explicit stack is like a a temp storage to store nodes that need to be processed and once you process a node you remove it and add its children to the stack then when you reach an Empty (a leaf) you just remove and that's how you finally end up with an empty stack [] and you would just return the current max (m) so far. Is that correct? – SpaceMonkey Jan 17 '14 at 16:40
oh I understand it now, you essentially examine, remove, add children. The loop finally stops adding more when it hits a leaf. Every time you hit a node you check if it has greater level than the current max and you update the max. Eventually you return the final max – SpaceMonkey Jan 17 '14 at 16:48

score 0 · Answer 2 · answered Jan 17 '14 at 15:47

In pragmatic cases the solution is to use a balanced tree, which limits the depth to some multiple of log(n). Even for very large n, log(n) is small enough that you won't run out of stack space.

Otherwise see the SO page linked by Kadaku. It has ridiculously good answers to the question.

score 0 · Answer 3 · answered Mar 19 '17 at 13:45

I already answered similar question once. Reposting the solution:

There's a neat and generic solution using fold_tree and CPS - continuous passing style:

let fold_tree tree f acc =
  let loop t cont =
    match tree with
    | Leaf -> cont acc
    | Node (x, left, right) ->
      loop left (fun lacc ->
        loop right (fun racc ->
          cont @@ f x lacc racc))
  in loop tree (fun x -> x)

let depth tree = fold_tree tree (fun x dl dr -> 1 + (max dl dr)) 0

OCaml binary tree depth with no stack overflow

3 Answers3