How to do tail recursion for a binary tree?

Question

If you have a binary tree, how can you iterate through (using in order) it using tail recursion? I know that tail recursion involves you to calculate the new value as you iterate, and then when you reach the base case, you just return the accumulation. But how do you do this for a tree, when you have to call the function call twice?

Any recursive function can be converted to tail recursive by using CPS. This question shows how to do binary tree processing in OCAML with tail recursion. — Barmar
@Barmar It's funny how often I hear "we can achieve tail recursion using CPS". It's not actually true for the Scheme definition of proper tail recursion, which specifies that unbounded tail recursion should not use unbounded memory. If the CPS describes a true tail-recursive process, that would indeed apply; otherwise, your chain of continuations would be of unbounded length. — Chris Jester-Young

Chris Jester-Young Chris Jester-Young · Accepted Answer · 2013-02-11T04:05:41

Assuming a depth-first left-to-right traversal, you cannot use tail recursion for the left-hand branch, but you can use it for the right-hand branch.

Example Scheme code (assuming that your tree has three accessor functions, value, left, and right):

(define (collect-in-order tree)
  (define (collect node result)
    (if node
        (collect (right node)
                 (cons (value node)
                       (collect (left node) result)))
        result))
  (reverse (collect tree '())))

The (collect (right node) ...) is in tail position, so that is a tail call.

You can also do a right-to-left traversal, in which case it's the leftward descents that are tail-recursive:

(define (collect-in-order tree)
  (let collect ((node tree)
                (result '()))
    (if node
        (collect (left node)
                 (cons (value node)
                       (collect (right node) result)))
        result)))

How to do tail recursion for a binary tree?

1 Answers