Programming Praxis

9 Responses to “Binary Tree Traversal”

1. Maxime said

   October 18, 2013 at 10:12 AM

   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

   October 18, 2013 at 10:22 AM

   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

   October 18, 2013 at 2:39 PM

   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. Adolfo Pérez Álvarez (@xardon) said

   October 20, 2013 at 12:28 PM

   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

   October 30, 2013 at 7:45 PM

   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

   November 8, 2013 at 2:13 PM

   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

   November 8, 2013 at 2:14 PM

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

   January 4, 2014 at 4:45 AM

   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. Building a BST from a depth-first preorder list in Haskell more idiomatically | Stackforum.com said

   January 8, 2014 at 7:20 PM

   […] 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: […]