Classroom practice: Binary trees.

Preparation for the practice:

• The lecture notes on recursion should be reviewed.
• The lecture notes on trees should be reviewed.

Building trees

Let us insert the following numbers into a binary search tree, in the given order, without balancing the tree: 5, 8, 3, 6, 7, 2, 9, 1. Draw the resulting binary tree!

            o
           / \
          o   o
         /   / \
        o   o   o
       /     \
      o       o

            3
           / \
          4   9
         /   / \
        2   6   5
       /     \   \
      1       7   0

Define the appropriate type for the following binary trees!

• Binary tree to store words and the number of their occurrences.
• Binary tree to store names and phone numbers (the name can be arbitrary long). (Mind that it is not enough to use integers for storing phone "numbers")
• We would like to decode Morse code as fast as possible with a binary tree. The two possible characters in Morse code are "." and "-". Depending on the next Morse character we can either go to the left (".") or to the right ("-") in this tree. When the character sequence ends, the corresponding latin letter can be found in the current node of the tree.

Let us use the type defined in the previous exercise to store contacts consisting of names and phone numbers in a binary search tree, ordered by the names. Create a C function that receives a pointer to the root of the tree and lists the phone numbers of all people called "Smith", in lexicographical ordering! (It is logical to store names 'family name first', as e.g. "Miller, Arthur".)

Let us determine the height (aka depth) of a binary tree!

Write a function to check whether two binary trees are equal or not.