C Exercises 3

Binary search tree

Problem 1

Look up the binary search tree on wikipedia / k&R (not sure whether it is present in k&r)

Create a structure to store the node of a binary search tree:

       struct node {
              int dat;
              struct node *left, *right;
       };

Modify the new_node function appropriately.

Rewrite the append function recursively (parameters and return value remain the same) so that it generates a binary search tree. For example:

               h = append(h, new_node(40));
               h = append(h, new_node(30));
               h = append(h, new_node(50));

will create a binary search tree with root node 40, left node 30 and right node 50.

Problem 2

There are three standard ways to "print" the nodes of a tree - inorder, pre-order and post-order. Write recursive functions to implement all three.

Problem 3

Write a recursive function to find out total number of nodes of a binary search tree

Problem 4

Write a recursive function to compute "height" of a binary search tree.