SML - How to create a list out of a postorder scan of a tree

Question

How to implement a function in SML which gets a tree and returns a list. The list consists of the values in the tree nodes according to postorder scan of the tree.

The tree datatype is:

datatype 'a Tree = Leaf | Branch of 'a * 'a Tree * 'a Tree;

Answer 1

That can be done simply by:

 fun createList(Leaf) = []
=   | createList(Branch(el, left, right)) = createList(left) @ createList(right) @ [el];

If you have a branch first visit it's left subtree (createList(left)), then it's right subtree (createList(right)) and afterwards append the element el, so basically do what a postorder tree traversal does. If you want to create a list from a Leaf (an empty tree) the result would be an empty list.

Answer 2

A more efficient solution:

local
   fun helper Leaf result = result
     | helper (Branch (el, left, right)) result = helper left (helper right (el::result))
in
   fun createList tree = helper tree nil
end

This is more efficient because @ has to completely unwind its left-hand argument to prepend it to the right-hand argument, which becomes very expensive if you are repeatedly applying it to longer and longer lists. By contrast, by using a helper function that prepends a subtree's postorder traversal onto a passed-in list, you can build the entire list just once.