Search code examples
listtreesmlsmlnj

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

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;
Solution

  • 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.