Solutions for those exercises.

Exercises

1. Consider the following tree:

   

   1. Explain why it is not a binary search tree.

   2. Pick one among inorder, preorder and postorder traversal, and give

      1. A brief description of how it proceeds,

      2. What it would produce for the given tree.

2. Consider the following implementation of “random” binary trees:

   public class RBTree<T>
   {
    
   private class Node
       {
       public T Data { get; set; }
       public Node left;
       public Node right;
       public Node(
           T dataP = default(T),
           Node leftP = null,
           Node rightP = null
           )
           {
               Data = dataP;
               left = leftP;
               right = rightP;
           }
       }
    
   private Node root;
    
   public RBTree()
       {
           root = null;
       }
    
   public void Insert(T dataP)
       {
           root = Insert(dataP, root);
       }
    
   private Node Insert(T dataP, Node nodeP)
       {
           if (nodeP == null)
           {
               return new Node(dataP, null, null);
           }
           else
           {
               Random gen = new Random();
               if(gen.NextDouble() > 0.5)
               {
                   nodeP.left = Insert(dataP, nodeP.left);
               }
               else
               {
                   nodeP.right = Insert(dataP, nodeP.right);
               }
           }
           return nodeP;
       }
   }

   Note that the Insert(T dataP, Node nodeP) method uses the gen.NextDouble() > 0.5 test that will be randomly true half of the time, and false the other half.

   1. Explain the T dataP = default(T) part of the Node constructor.

   2. Write a ToString method for the Node class, remembering that only a node Data needs to be part of the string returned.

   3. Write a series of statements that would

      1. create a RBTree object,
      2. insert the values 1, 2, 3, and 4 in it (in this order).

   4. Make a drawing of a possible RBTree obtained by executing your code.

   5. Write a Find method that takes one argument dataP of type T and returns true if dataP is in the RBtree calling object, false otherwise.

3. Given the usual implementation of Node:

   private class Node
   {
       public T Data { get; set; }
       public Node left;
       public Node right;
    
       public Node(T dataP = default(T), Node leftP = null, Node rightP = null)
       {
           Data = dataP;  left = leftP; right = rightP;
       }
   }

   Write an Height property for Node (i.e., a way of computing the longest distance between the calling Node and a leaf).

4. Considering an implementation of binary search trees where T realizes the IComparable<T> interface (i.e., where the .CompareTo method can be used to compare values), write a ValueGreaterThan method that

   • takes an argument dataP of type T,
   • returns
     • true if there is a value greater than or equal to dataP in the binary search tree,
     • false if there is no value greater than dataP in the binary search tree, or if the tree is empty.