0

Good day, I am new to java and new to this forum but I request a bit of help. I am learning java on my own and I am currently learning binary trees. I have come an algorithm that is giving me a little issue. It is a binary tree code that basically inserts five nodes into a tree structure and then traverses the tree. My problem is that I do not understand what kind of tree structure is being created. Is it a balanced on or and unbalanced one. Also how can you tell whether it is one or the other and would that affect the type of traversal the algorithm is conducting. Can you help?

Here is the code:

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);
        }
     }
  }
2
  • 1
    A balanced tree is when all brackets are about the same size (or at least same order of magnitude). The consequence is that you get a O(log N) traversal in the worst case. In a unbalanced tree you can get a O(N) in the worst case.
    – Mandrill
    Oct 2, 2016 at 2:56
  • 2
    Before asking here, you should have read the wikipedia page on balanced trees Oct 2, 2016 at 6:30

1 Answer 1

4

Your code, as written, will produce a tree that looks like this:

   5
  / \
 /   \
1     8
 \   /
  3 6
     \
      9

A properly balanced tree looks like this:

     6
    / \
   /   \
  3     8
 / \     \
1   5     9

So, no. this is not balancing your binary tree. This is simply constructing a sorted binary tree with a balance that is totally dependent on the sequence of insertion.

Depending on the order of insert() calls you could easily end up building:

1
 \
  3
   \
    5
     \
      6
       \
        8
         \
          9

You have no code to rebalance the tree.

I recommend you give this a read:

http://www.stoimen.com/blog/2012/07/03/computer-algorithms-balancing-a-binary-search-tree/

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.