NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX

Converting trees to lists

There are many ways to convert a tree into a list. These are termed traversal strategies for trees. Here we will look at three: preorder, inorder and postorder.

Definition (Preorder traversal)

First visit the root, then traverse the left and right subtrees in preorder.

Definition (Inorder traversal)

First traverse the left subtree in inorder, then visit the root and finally traverse the right subtree in inorder.

Definition (Postorder traversal)

First traverse the left and right subtrees in postorder and then visit the root.

Exercise

Define 'a tree -> 'a list functions, preorder, inorder and postorder.


NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX