Binary Tree Traversal

October 18, 2013

The pre-order and post-order functions are simple recursive functions on the structure of the tree; notice that we are careful to avoid nulls in the tree structure:

(define (preorder t)
  (if (null? t)
      (list)
      (append (list (car t))
              (if (pair? (cdr t))
                  (preorder (cadr t))
                  (list))
              (if (and (pair? (cdr t))
                       (pair? (cddr t)))
                  (preorder (caddr t))
                  (list)))))

(define (postorder t)
  (if (null? t)
      (list)
      (append (if (pair? (cdr t))
                  (postorder (cadr t))
                  (list))
              (if (and (pair? (cdr t))
                       (pair? (cddr t)))
                  (postorder (caddr t))
                  (list))
              (list (car t)))))

And here are the functions applied to the sample tree shown on the previous page:

> (define t '(8 (3 (1) (6 (4) (7))) (10 () (14 (13) ()))))
> (preorder t)
(8 3 1 6 4 7 10 14 13)
> (postorder t)
(1 4 7 6 3 13 14 10 8)

Reconstructing the tree is the opposite operation of traversing the tree. The left-most element of the pre-order sequence is the root of the tree. Nodes less than the root are in the left child of the tree, and nodes greater than the root are in the right child of the tree, so the solution makes the first node in the pre-order sequence the root of the tree and calls itself recursively on the the lesser portion of the sequence and the greater portion of the sequence. Reconstructing a tree based on the post-order sequence is the opposite, with the root of the tree at the last element of the list:

(define (prebuild xs)
  (cond ((null? xs) (list))
      ((null? (cdr xs)) (list (car xs)))
        (else (call-with-values
          (lambda ()
            (split-while
              (lambda (x) (< x (car xs))) (cdr xs)))
          (lambda (lo hi)
              (list (car xs) (prebuild lo) (prebuild hi)))))))

(define (postbuild xs)
  (cond ((null? xs) (list))
        ((null? (cdr xs)) (list (car xs)))
        (else (call-with-values
          (lambda ()
            (split-while
              (lambda (x) (< x (last xs))) (but-last xs)))
            (lambda (lo hi)
              (list (last xs) (postbuild lo) (postbuild hi)))))))

We use the convenience functions last and but-last:

(define (last xs) (car (reverse xs)))

(define (but-last xs) (reverse (cdr (reverse xs))))

And here are some more examples:

> (prebuild (preorder t))
(8 (3 (1) (6 (4) (7))) (10 () (14 (13) ())))
> (postbuild (postorder t))
(8 (3 (1) (6 (4) (7))) (10 () (14 (13) ())))

We used split-while from the Standard Prelude. You can run the program at http://programmingpraxis.codepad.org/s86rBxGF.

About these ads

Pages: 1 2

9 Responses to “Binary Tree Traversal”

  1. Maxime said

    My solution for the two first functions, in 105 bytes of JavaScript:

    // ordering function
    // parameters: source tree, destination array, direction (pre:1, post: 0)
    o=function(b,c,d){void 0!==b&&(isNaN(b)?(d&&c.push(b[1]),o(b[0],c),o(b[2],c),d||c.push(b[1])):c.push(b))}

    // tests
    tree = [[1,3,[4,6,7]],8,[,10,[13,14,]]];
    pre_order_array = [];
    post_order_array = [];

    o(tree, pre_order_array, 1);
    console.log(pre_order_array); // -> [8, 1, 4, 7, 6, 3, 13, 14, 10]

    o(tree, post_order_array, 0);
    console.log(post_order_array); // -> [1, 4, 7, 6, 3, 13, 14, 10, 8]

  2. Maxime said

    Sorry, I meant:

    o=function(b,c,d){void 0!==b&&(isNaN(b)?(d&&c.push(b[1]),o(b[0],c,d),o(b[2],c,d),d||c.push(b[1])):c.push(b))}

    This function returns a correct array for pre-order.

  3. Peter Salvi said

    Common Lisp solution:

    ;;; Node; (VALUE LEFT RIGHT)
    
    (defun preorder (tree)
      (when tree
        (cons (first tree) (append (preorder (second tree)) (preorder (third tree))))))
    
    (defun postorder (tree)
      (when tree
        (append (postorder (second tree)) (postorder (third tree)) (list (first tree)))))
    
    (defun tree-insert (tree a)
      (if (null tree)
          (list a nil nil)
          (cond ((= a (first tree)) tree)
                ((< a (first tree))
                 (list (first tree) (tree-insert (second tree) a) (third tree)))
                (t (list (first tree) (second tree) (tree-insert (third tree) a))))))
    
    (defun tree-from-preorder (lst)
      (reduce #'tree-insert lst :initial-value nil))
    
    (defun tree-from-postorder (lst)
      (reduce #'tree-insert (reverse lst) :initial-value nil))
    
  4. structure ListX = struct
      fun span f []      = ([], [])
        | span f (x::xs) =
          if f x
          then
    	  let
    	      val (ys, zs) = span f xs
    	  in
    	      (x::ys, zs)
    	  end
          else
    	  ([], x::xs)
    	  
      fun splitAtLast []      = raise List.Empty
        | splitAtLast [x]     = ([], x)
        | splitAtLast (x::xs) =
          let
    	  val (ys, y) = splitAtLast xs
          in
    	  (x::ys, y)
          end
    end
    
    datatype 'a tree =
    	 Tree of 'a * 'a tree * 'a tree
           | MTTree
    
    fun traverse f g e MTTree           = e
      | traverse f g e (Tree (a, l, r)) =
        g (f a) (traverse f g e l) (traverse f g e r)
    
    fun pre t =
        let
    	fun g e ls rs = e::(ls@rs)
        in
    	traverse (fn x => x) g [] t
        end
    
    fun post t =
        let
    	fun g e ls rs = (ls@rs)@[e]
        in
    	traverse (fn x => x) g [] t
        end
    
    datatype traversal = Pre | Post
    
    local
        fun root Pre  (x::xs) = (xs, x)
          | root Post xs      = ListX.splitAtLast xs
    in
      fun recons _ [] = MTTree
        | recons t xs =
          let
    	  val (ys, y) = root t xs
    	  val (l, r)  = ListX.span (fn a => a < y) ys
          in
    	  Tree (y, recons t l, recons t r)
          end
    end
          
    val a = pre (recons Pre [8, 3, 1, 6, 4, 7, 10, 14, 13])
    	= [8, 3, 1, 6, 4, 7, 10, 14, 13]
    val b = post (recons Post [1, 4, 7, 6, 3, 13, 14, 10, 8])
    	= [1, 4, 7, 6, 3, 13, 14, 10, 8]
    
  5. Josef Svenningsson said

    For the task of recreating the tree from a preorder traversal I managed to come up with a function which traverses the list once and doesn’t allocate anything extra except the tree (well, it does allocate tuples, but they can be removed). So that’s quite nice, but I failed to do the same thing with the postorder traversal.

    fromPreOrder :: Ord a => [a] -> Tree a
    fromPreOrder [] = Leaf
    fromPreOrder (a:as) = Branch a l (fromPreOrder bs)
      where
        (l,bs) = lessThan a as
    
    lessThan n [] = (Leaf,[])
    lessThan n all@(a:as)
      | a >= n    = (Leaf,all)
      | otherwise = (Branch a l r,cs)
      where (l,bs) = lessThan a as
            (r,cs) = lessThan n bs
    
    
  6. Marc Young said

    In xquery:

    declare function local:post-order(
    $tree as node()
    ) {
    let $seq :=
    if (local:has-children($tree)) then (
    let $left := $tree/node()[1]
    let $right := $tree/node()[2]
    return
    (
    local:post-order($left),
    local:post-order($right),
    $tree/@val/fn:string()
    )
    ) else (
    $tree/@val/fn:string()
    )
    return $seq
    };

    declare function local:pre-order(
    $tree as node()
    ) {
    let $seq :=
    if (local:has-children($tree)) then (
    let $left := $tree/node()[1]
    let $right := $tree/node()[2]
    return
    (
    $tree/@val/fn:string(),
    local:pre-order($left),
    local:pre-order($right)
    )
    ) else (
    $tree/@val/fn:string()
    )
    return $seq
    };

    declare function local:has-children(
    $node as node()*
    ) {
    if (fn:count($node) gt 1) then (
    fn:error(xs:QName(“ERROR”), “not a single node”)
    ) else (
    if ($node/node()) then (
    fn:true()
    ) else (
    fn:false()
    )
    )
    };

    let $tree :=

    return

    {local:pre-order($tree)}
    {local:post-order($tree)}

  7. Marc Young said

    My formatting got fubar apparently…. the functions are correct though

  8. treeowl said

    Congrats to Josef Svenningsson for finding an O(n) prebuild! The tree it produces doesn’t quite match the specified format, but it’s easy to write a function to convert it to a tree that stores things in its leaves, so that’s no big deal. postbuild seems inherently harder. I have the feeling it should be possible to write something very similar to prebuild to apply to a reversed postorder traversal, but I haven’t managed to make it work out quite right yet. I will give it another go later.

  9. […] This submission to Programming Praxis gives an O(n) function that “undoes” a preorder traversal of a binary search tree, converting a list back into a tree. Supplying the missing data declaration: […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 611 other followers

%d bloggers like this: