Assignment 5

• A binary search tree is either empty, or it consist of a node storing a key (the root of the tree), and a left and right subtree, such that all keys in the left subtree are smaller than the key in the node, and all keys in the right subtree are bigger.
• Trees can be traversed in different order:
  • To print a tree in (left-to-right) preorder, you first print the root, then the left subtree, then the right subtree
  • To print a tree in (left-to-right) postorder, you first print the left subtree, then the right subtree, then the root
  • To print a tree in natural order, you first print the left tree, then the root, then the right tree
• Design a data structure for binary search trees with int keys, using dynamic memory handling.
• Implement functions to:
  • Insert keys into the tree (ignoring keys already in the tree)
  • Print a tree in preorder, natural order, and postorder
  • Free the memory taken up by the tree
• Use this datatype and the functions from integerio to write a program that reads a list of integers from stdin into a tree, and prints that tree in the three different orders.
• You can use the code from the linear list example as a base. The complete code will be available from the course homepage.