Classroom practice: Binary trees.

Gábor Horváth / Zsolt Kohári · 2020.12.11.

Binary trees and related recursive algorithms.

Preparation for the practice:

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

1. Properties of trees

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!

Solution

            5
           / \
          3   8
         /   / \
        2   6   9
       /     \
      1       7

Properties of trees

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

What is the height of this tree? How many leaves does it have?

Traversing trees

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

Is the binary tree above a binary search tree? In which order are the elements of the tree visited in case of a) inorder b) postorder c) preorder traversal?

2. Types

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.

Solution

typedef struct Word {
    char word[30+1];
    int occurrences;

    struct Word *left, *right;    /* left and right ascendants */
} Word;
typedef struct Contact {
    char *name;                 /* arbitrary long name */
    char phone[21];             /* phone number of size 20 characters max. */
    struct Contact *left, *right;
} Contact;
typedef struct Morse {
    char letter;

    struct Morse *dot, *dash;     /* the next symbol is either a dot or a dash */
} Morse;

3. Traversing trees

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".)

Solution

The strncmp() function will be useful in this task, to compare two strings up to a given number of characters.

Let us traverse the tree using the inorder traversal, and print all data if the name is appropriate. Due to the inorder traversal the nodes will be visited in a lexicographical order.

void print_smith(Contact *root) {
    if (root == NULL) return;

    print_smith(root->left);
    /* 5 = strlen("Smith") */
    if (strncmp("Smith", root->name, 5) == 0)
        printf("%s %s\n", root->name, root->phone);
    print_smith(root->right);
}

4. Height of trees

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

Solution

The definition of the height: the distance of the leaf that is the farthest away from the root. This problem can be formulated recursively as follows.

  1. The height of an empty tree is 0.
  2. Let us compute the height of the left and the right sub-trees.
  3. Let us take the maximum of them.
  4. Let us add 1 to the result (the root). 
typedef struct BinTree {
    int data;

    struct BinTree *left, *right;
} BinTree;

int height(BinTree *root) {
    int left, right, max;

    if (root == NULL) return 0;    /* 1 */

    left  = height(root->left);    /* 2 */
    right = height(root->right);
    /* which side is higher? */
    max  = left > right ? left : right;  /* 3 */

    return max + 1;                  /* 4 */
}

5. Comparing trees

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

Solution

The comparison can be done as follows. Our function receives two trees. If both trees are empty (NULL), the function needs to return true, since two empty trees are treated as equal. If one of the trees is empty and the other is not, then we can be sure that the two trees are not equal (whatever is stored in the non-empty one). If none of the two trees are empty, we have to compare them: they are equal when the data stored in their root elements are equal, and their left sub-trees are equal, and their right sub-trees are equal.

Note that when two trees give the same sequence for in-order traversal, they can still be different.

bool equal(BinTree *first, BinTree *second) {
   if (first == NULL && second == NULL)  /* two empty trees are equal */
      return true;
   if (first != NULL && second == NULL)  /* empty vs. non-empty -> not equal */
      return false;
   if (first == NULL && second != NULL)  /* same here */
      return false;

   return first->data == second->data           /* the data is the same in the root */
       && equal(first->left, second->left)      /* and the left sub-tree is the same */
       && equal(first->right, second->right);   /* and the right sub-tree is the same */
}