How to Determine if a Binary Tree is Balanced or Unbalanced

binary treejava

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);
        }
     }
  }

Best Answer

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/