Exercises

1. Consider the following tree:

   

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

      Solution

      The left child of the node with value 13 has value 14, which is greater than 13, hence violating the binary search tree principle that values in the left sub-tree should be strictly less than the value in the root of the subtree. The same goes for 12.

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

      1. A brief description of how it proceeds,

         Solution

         One among the following:

         • Inorder traversal processes (recursively) first the left subtree, then the data at the root, then the right subtree.
         • Preorder traversal processes (recursively) first the data at the root, then the left subtree, then the right subtree.
         • Postorder traversal processes (recursively) first the left subtree, then the right subtree, then the data at the root.

      2. What it would produce for the given tree.

         Solution

         One among the following:

         • Inorder gives 6, 10, 14, 13, 12
         • Preorder gives 10, 6, 13, 14, 12
         • Postorder gives 6, 14, 12, 13, 10

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.

      Solution

      This makes the first argument of the constructor optional: if no value is provided, then the default value for T is used. For example, for int, then 0 would be used.

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

      Solution

       public override string ToString()
       {
           return Data.ToString();
       }

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

         Solution

          RBTree<int> btree = new RBTree<int>();
          btree.Insert(1);
          btree.Insert(2);
          btree.Insert(3);
          btree.Insert(4);

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

      Solution

      Any binary tree containing 1, 2, 3 and 4, with 1 at the root, 2 a child of 1, 3 a child of 1 or 2, and 4 a child of 1, 2 or 3, is correct. One such example is:

      

   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.

      Solution

       public bool Find(T dataP)
       {
           bool found = false;
           if (root != null)
           {
               found = Find(root, dataP);
           }
           return found;
       }
       
       private bool Find(Node nodeP, T dataP)
       {
           bool found = false;
           if (nodeP != null)
           {
               if (nodeP.Data.Equals(dataP))
               {
                   found = true;
               }
               else
               {
                   found =
                   Find(nodeP.left, dataP)
                   || Find(nodeP.right, dataP);
               }
           }
           return found;
       }

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

   Solution

   The one provided in the lecture notes is:

           public int Height
           {
               get
               {
                   int height = 0;
                   if (left != null && right != null)
                   {
                       height = Math.Max(left.Height, right.Height) + 1;
                   }
                   else if (left != null)
                   {
                       height = left.Height + 1;
                   }
                   else if (right != null)
                   {
                       height = right.Height + 1;
                   }
                   // The last case is if both children
                   // are null, in which case the height
                   // remains 0.
                   return height;
               }
           }

   (Download this code)

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.

   Solution

   The one provided in the lecture notes is:

    
       public bool ValueGreaterThan(T dataP)
       {
           bool returned = false;
           if(root != null)
           {
               returned = ValueGreaterThan(dataP, root);
           }
           return returned;
       }
    
       private bool ValueGreaterThan(T dataP, Node nodeP)
       {
           bool returned = false;
           if (nodeP != null)
           {
               if (dataP.CompareTo(nodeP.Data) > 0) // dataP > nodeP.Data
                   return ValueGreaterThan(dataP, nodeP.right);
               // We only need to go right, since values will decrease
               // if we go left.
               else
                   returned = true;
           }
           return returned;
       }

   (Download this code)