An interesting question that I came across a few days ago: is there an elegant functional programming solution to build a (node-labelled) binary tree from a list?
The resulting tree should be left-balanced, i.e. every level of nodes in the tree should either be filled completely or, in case of the lowest one, filled from left to right. Also, a level-order traversal of the tree (i.e. top-to-bottom, left-to-right) should give the original list.
Example: the list 1,2,3,4,5 should result in
1
2 3
4 5
The obvious solution is to convert the list to an array, assign the zeroth value to the root and then, recursively, for a node n, give the children the values 2n+1 and 2n+2.
But I was wondering: is there a more "functional" way that doesn't require an auxiliary array?
Thoughts expressed in rsr5 scheme
My initial thoughts involves an infinite tree whose nodes are functions that take a value and a tree and insert that value into that tree in the same place the function is found. You could then do a fold2 like recursion over the list and a level-oder transversal of the function tree applying the successive function to the successive list elements to accumulate a binary tree. (Only works with lazy evaluation though)
Seemed a bit unwieldy though so I revised the thought to a tree of data that could be fed to a function like ('l 'r 'l) or something that could tell where to insert and index.
(define (insert-new ls-and-rs tree)
(cond ((or (empty-tree?) (null? ls-and-rs))
(if (and (empty-tree?) (null? ls-and-rs))
(make-tree x emptyTree emptyTree)
(error "insert-new can only insert at emptyree")))
((sybol=? (car ls-and-rs) 'l)
(make-tree (node tree)
(insert-new (cdr ls-and-rs)
(left-tree tree))
(right-tree tree)))
((sybol=? (car ls-and-rs) 'r)
(make-tree (node tree)
(left-tree tree)
(insert-new (cdr ls-and-rs)
(right-tree tree))))
(else (error "insert-new expected 'l or 'r, recieved "
(car ls-and-rs))))))
Then I saw you could build that from the index itself. An index if 1 is the head of the tree. Otherwise if it's odd it's a right branch of a node. If it's even a left branch. The index of it's parent is always the floor of the child divided by two. From that knowledge you can build an inserter or accessors with merely an index.
(define (branch-order i)
(let loop ((i i) (accum '()))
(cond ((i = 1) accum)
((odd? i) (loop (quotient i 2) (cons 'r accum)))
(else (loop (quotient i 2) (cons 'l accum))))))
From there it's a straightforward recursion
(define (list->tree list)
(let loop ((list list) (i 1) (tree emptyTree))
(cond ((null? list) tree)
(else (loop (cdr list)
(+ i 1)
(insert-new (branch-order i) tree))))))
Of course the easiest way is if you can accept a minimum-depth binary tree. A depth tree lists it's minimum depth in addition to it's nodes and branches. The insert would then insert into the left sub-tree unless the minimum depth of the right sub-tree was less than that of the left.
(define (list->d-tree list)
(fold-left (flip balanced-insert) emptyTree list))
(define (balanced-insert x d-tree)
(cond ((= 0 (d-d-tree d-tree))
(mk-d-tree x emptyTree emptyTree)
((= 1 (- (d-d-tree d-tree) (d-d-tree (l-d-tree d-tree))))
(mk-d-tree (n-d-tree d-tree)
(balanced-insert x (l-d-tree d-tree))
(r-d-tree d-dtree)))
(else
(mk-d-tree (n-d-tree d-tree)
(l-d-tree d-tree)
(balanced-insert x (r-d-tree d-dtree))))))
(define (mk-d-tree n l r)
(let ((d-l (d-d-tree l))
(d-r (d-d-tree r)))
(list n l r (+ 1 (min d-l d-r)))))
(define (n-d-tree d-tree)
(car d-tree))
(define (l-d-tree d-tree)
(cadr d-tree))
(define (r-d-tree d-tree)
(caddr d-tree))
(define (d-d-tree d-tree)
(if emptyTree? d-tree)
0
(cadddr d-tree)))
(define (emptyTree? tree)
(null? tree))
(define emptyTree '())
(define (flip f)
(lambda (a b)
(f b a)))
TLdr; use a minimum depth tree and insert to the leftmost minimum depth.