Tree Recursion

Writing a tree-recursive program requires answering several questions:

• What are the branches?
  • first and rest
  • lhs and rhs

• How should results from branches be combined?
  • additive
    • ordered, e.g. consing onto ordered list
    • unordered, e.g addition or union
  • structural
  • search: first one that works

• Is an ordering of the tree search required by the domain?
  • preorder: parent before children
  • inorder: one child, parent, other child
  • postorder: children first, then parent, e.g. must evaluate children before performing operation on them