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?

Answer 1

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)))