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. Post your findings to the discussion forum and review and respond to the postings of your peers.

If you have arrived at a different answer or analysis than your peers, discuss your findings with your peers and attempt to determine whose analysis is most accurate.

Answer 1

Tree structure that is being created using the algorithm is binary search tree.

We can say that it is creating a binary search tree, because when the node value is less than current node then we move to left of tree and if the node value is greater than current node value we move to the right of the tree.

This is the algorithm that is used to insert node in a binary search tree.

Below image is the binary search tree that is created in the code above

Order of traversal:-

Code is conducting an in order traversal on binary search tree.

We can say that because we are following (left, root, right) traversal order, that means traverse left, print root and then traverse right.

And also from console output we can conclude that it is in order traversal, because in order traversal of a binary search tree is always in sorted order.
Here is the console output for traversal.

Traversing tree
Traversed 1
Traversed 3
Traversed 5
Traversed 6
Traversed 8
Traversed 9

Complexity analysis:-

Insert function time complexity:-

As we know that binary search tree is not a balanced tree, that means that the height of the tree can grow upto O(n) for n nodes. So worst case complexity to insert a node will be when the height of tree is n and the node we are inserting is inserted at the end of the tree. That will take O(n) time.

So worst case complexity for insert is O(n)

printOrder function will traverse every node exactly once. So for a binary search tree of n nodes, it will take theta(n) time.