Binary Tree Traversal
October 18, 2013
In a previous exercise, we wrote a small library for maintaining binary search trees, including a function that traversed the tree in order. In today’s exercise we will write functions that traverse a tree in pre-order and post-order.
Given the tree shown at right, a pre-order traversal visits the node in this order: 8 3 1 6 4 7 10 14 13. At each level of the tree, pre-order traversal first handles the current node, then calls itself recursively on the left child, then calls itself recursively on the right child.
A post-order traversal visits the nodes in this order: 1 4 7 6 3 13 14 10 8. At each level of the tree, post-order traversal calls itself recursively on the left child, then calls itself recursively on the right child, then finally handles the current node.
In addition to traversing a tree in pre-order or post-order, you should write functions that reconstruct the original tree given a list of the tree nodes in pre-order or post-order.
Your task is to write the four functions described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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]
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.
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))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]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.
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)}
My formatting got fubar apparently…. the functions are correct though
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.
[…] 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: […]