Using Jeliot, execute the following tree algorithm: import Prog1Tools.IOTools; c

Question

Using Jeliot, execute the following tree algorithm:

     import Prog1Tools.IOTools;
     
     class Node {
          Node left;
          Node right;
          int value;

          public Node(int value) {
              this.value = value;
          }
     }

     public class GeneralTreeTest {
       public static void main(String[] args) {

          // build a simple tree add 5 nodes to the tree
          Node root = new Node(5);
          System.out.println("Tree Example");
          System.out.println("Building tree with root value " +       root.value);
          insert(root, 1);
          insert(root, 8);
          insert(root, 6);
          insert(root, 3);
          insert(root, 9);
          System.out.println("Traversing tree ");
          printOrder(root);

     }

     public static void insert(Node node, int value) {
          if (value < node.value) {
            if (node.left != null) {
              insert(node.left, value);
            } else {
              System.out.println(" Inserted " + value + " to left of "
                  + node.value);
              node.left = new Node(value);
            }
         } else if (value > node.value) {
            if (node.right != null) {
              insert(node.right, value);
            } else {

                 System.out.println(" Inserted " + value + " to right of "
                      + node.value);
                 node.right = new Node(value);
             }
          }
     }

     public static void printOrder(Node node) {
        if (node != null) {
           printOrder(node.left);
           System.out.println(" Traversed " + node.value);
           printOrder(node.right);
        }
     }
}

This algorithm first inserts five nodes into a tree structure and then traverses the tree. Using the Jeliot environment, load, compile and execute this java algorithm to understand its operation. Determine the kind of tree structure that is being created and determine what kind of traversal the algorithm is conducting.

Finally, conduct an Asymptotic analysis for the provided algorithm and report your analysis including Big O, Big Omega, or Big Theta as appropriate.

Explanation / Answer

Tree Structure: Binary Search Tree

We can see in insert method that a node is recursively inserted to the left of a node if it is smaller in value than the node and similarly to the right if the value is greater than that of the node.

Traversal Type: InOrder

You can see in printOrder method that we first print nodes on the left than the root node and then the nodes of the right subtree. So this is exactly same as what we do in the inorder traversal of tree.

----------------------------

Analysis:

Insertion: O(n)

In the case when the input is sorted in some order. For example: 1,2,3,4,5. Inserting these. we will always have to travel to the rightmost end of tree so in the worst case we would have to traverse all the nodes in tree to insert new node.

printOrder: O(n)

To get a feel of why printOrder is O(n) you can see that in traversing tree. every node gets visited. So printOrder gets called for every node and the method itself does constant operation. So you simply do constant time operation for every node.

More mathematically we can form the recurrence relation of time.

O(n) = O(1) + O(l) + O(n-l)

----------------------------------

In case of any doubts just comment down.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.