CODEWITHSUNDEEP
recursionlanguage-agnosticbinary-treetail-recursion
omega
omega

Reputation: 43953

How to do tail recursion for a binary tree?

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?

Upvotes: 5

Views: 5136

Answers (1)

C. K. Young
C. K. Young

Reputation: 223193

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

Upvotes: 8

Related Questions