Plain English Explanation of Binary Tree with Java Code

Binary Tree is one of the most amazing data structure some one has come up with which I have a chance to learn it right now. Actually this was the most amazing of data structure I had to know. Guys, I really regret that during high school I think it was never be possible to learn linked list, hell, linked list is so easy :D. Okay, let’s learn binary tree!

Learning binary tree is challenging. Bilal helped me to understand the logic of this. Then, I decide to implement all the code, by myself without any prior knowledge of reading even a single example of binary tree code. Actually I also write a linked list app guided only by my logic without looking to any prior code, but linked list was really much easier than this.

If you want to imagine how I think binary tree is much harder. Then. Actually, after the class finished (my data structure class today is from 5-8PM) I go to Mushalla for Maghrib prayer with Bilal. Then I went eat at Iraqi restaurant (the Haneeth lamb just so delicious). After that I went back to the hostel, and I just realize I left my key in the lab. I go to the lab, my key is not there. I went back home bla bla bla open phone receive message from Ken that my key is with him. Oh thanks. You know what? during all the walk from here and there, what I think is only Binary Tree and I can’t wait any longer to try to implement this on my computer with my own logic. At the end, I did it ^^ (It takes me 2.30 hours to program this with no break). Give me 10 minutes for linked list 😛 Binary tree is, guys really, a great piece of work yet it is an actually simple data type.

An Introduction to Binary Tree

Binary Tree is a tree with maximum one root, and each root has maximum two child. The child that has no ‘child’ is called leaf. The child that has ‘child’ is called parent, so parent can be child of child of child of (…) of root.

Every node (be it child or parent, root or leaf, actually they all are node), has a key and a value (data). The value can be another abstract data type or a primitive data type. The key can only be non-zero integer value (character is an integer).

To insert a node, there is a rule on how to insert a node. We have to compare the key with the parent. If the child’s key is higher compared to the parent’s key, it have to be on the right edge of the parent, otherwise it will be on the left edge. Edges is a branch that connecting one node to the other to make associativity. The associativity is always one-to-one.

Let’s say. You want to insert 102 (char: f) in the tree. First, it compares with its first parent’s id (100, char: d). Because 102 > 100, then it will be on the right edge. According to this rule, the key that is ordered ascending, it will grow to the right side (have no left side at all). But, what happens when the key is ordered descending? (get your hands dirty!)

A tree is said to have n-level, in this tree: 5-level tree. Tree is said to be unbalanced if the number of child on each level is not equal, thus one side is deeper than the other side. The tree that is ordered ascending or descending is always unbalanced, and is actually no different with array, arraylist and/or linked list.

Coding

Now, let’s get into the interesting part. We will have three classes. Those classes are:

  1. Leaf.java (which is as usual Node in Linked List, with extended ability).
  2. BinaryTree.java (the logic of binary tree lives here).
  3. BinaryTreeApp.java (the implementation of BinaryTree class).

Leaf.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package latihan5;

/**
 *
 * @author adampbe
 */
public class Leaf<E> {
    protected E data;
    protected Leaf<E> right;
    protected Leaf<E> left;
    private int id;

    public Leaf()
    {
    this.data = null;
    this.right = null;
    this.left = null;
    }

    public Leaf(int id, E data)
    {
    this.id = id;
    this.data = data;

    this.right = null;
    this.left = null;
    }

    public void insert(Leaf<E> child)
    {
    int id_child = child.id;

    System.out.print("Inserting to the ");
    if (this.id < id_child)
    {
        System.out.print("right edge with " + child);
        this.right = child;
    }
    else
    {
        System.out.print("left edge with " + child);
        this.left = child;
    }

    System.out.println(" to parent " + this.toString());
    }

    public int getId() {return this.id;}

    //is right hand side empty? (null)
    public boolean isRHSEmpty() {return this.right==null;}
    public boolean isLHSEmpty() {return this.left==null;}

    @Override
    public String toString()
    {
    StringBuilder str = new StringBuilder();
    str.append("ID: ");
    str.append(this.id);
    str.append(". Content: ");
    str.append(this.data.toString());
    return str.toString();
    }
}

The code is quite obvious, though I will explain why I put the weird informational string whenever user tries to insert a new node. I just want the program to inform what happens when we do insert: at which branch of which parent is the operation took place.

BinaryTree.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package latihan5;

/**
 *
 * @author adampbe
 */
public class BinaryTree<E>
{
    private Leaf root;

    public BinaryTree()
    {
    root = null;
    }
    public BinaryTree(int id, E data)
    {
    root = new Leaf(id, data);
    }

    public Leaf get(int id)
    {
    Leaf current = root;

    for (;;)
    {
        if (current == null) return null;
        else
        {
        if (current.getId() == id) return current;
        else current = (current.getId() < id) ? current.right: current.left;
        }
    }
    }

    private Leaf getParent(int id)
    {
    Leaf current = root;
    Leaf parent = null;

    for (;;)
    {
        if (current == null) return parent;
        else {
        //before changing the current. this current will be the parent
        parent = current;
        current = (current.getId() < id) ? current.right : current.left;
        }
    }
    }

    public boolean insert(int id, E data)
    {
    Leaf newLeaf;
    if (this.root == null)
    {
        newLeaf = new Leaf(id, data);
        this.root = newLeaf;
    }
    else
    {
        //make sure every id is unique
        if (this.get(id) == null)
        {
        newLeaf = new Leaf(id, data);
        //get parent
        Leaf parent = this.getParent(id);
        //add the new leaf to this parent
        parent.insert(newLeaf);
        return true;
        }

    }

    return false;
    }

    //tracing tree down-the-hill from an id
    public void trace(int id)
    {
    Leaf leaf = get(id);
    if (leaf != null)
    {
        System.out.println("Starting to trace from leaf id " + id);
        System.out.println("->Tracing left: " + leaf.left);
        trace(leaf.left,"");
        System.out.println("->Tracing right: " + leaf.right);
        trace(leaf.right,"");
    }
    }

    private void trace(Leaf leaf, String pre)
    {
    if (leaf != null)
    {
        pre += "  ";
        if (leaf.left != null)
        {
        System.out.println(pre + "->Tracing left: " + leaf.left);
        trace(leaf.left, pre);      
        }
        if (leaf.right != null)
        {
        System.out.println(pre + "->Tracing right: " + leaf.right);
        trace(leaf.right, pre);     
        }
    }
    }
}

The description of method:

  • get() will return a node (if any) that has id id
  • getParent() will return a parent for a child with id id
  • insert() will add a new data item resulting in creating a new node.
  • When inserting, if the root is null, the new leaf will automatically be set as root.
  • When inserting, if the root is not null, then search for a ‘parent’. The rules of searching a parent has been explained in the above section.

BinaryTreeApp.java

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package latihan5;

/**
 *
 * @author adampbe
 */
public class BinaryTreeApp {
    public static void main(String[] args)
    {
    BinaryTree<String> bt = new BinaryTree<String>();

    bt.insert('d', "William Young");
    bt.insert('b', "Erra Amorta");
    bt.insert('f', "Pipit Rezita");
    bt.insert('a', "Kumara Tedjanegara");
    bt.insert('c', "Hew Zher Ken");
    bt.insert('e', "Saw Shih Wen");
    bt.insert('g', "Adam Pahlevi Baihaqi");
    bt.insert('k', "Wong Lai Wan");
    bt.insert('j', "Iqbal Agung");

    System.out.println("\nNow let's do tracing!");
    bt.trace('d');
    }
}

This is the demo class. Now let’s run. When we were inserting into the tree, we can see clearly the process taken:

To verify with our drawing previously, we can use trace() to trace the tree. Here are the output for tracing the tree starting at key ‘d’.

Is the drawing matches with the tracing output?

Hope

I hope, this program can help you learn and better understand binary tree. I hope, this tutorial will elevate you I don’t care in which level as long as you are elevated and becoming less frustrated with binary tree. My recommendation for you is to learn a simpler data type like Linked List first before going to Binary Tree. There is also kind of self-balancing tree like AVL, which my self not yet learn about it.

How about deleting a node, dude?

Deleting a node? Oh yah, I try to hide that from you because I still can’t implement that one.Okay, basically deleting a node involves many cases. We must consider all the cases that can happen. I need to study first about this. I already told you binary tree is challenging, many things need to be learn. Moreover, I have placed an order for a Java Hibernate book …yay can’t wait to read. So, please visit next time I will bring the deletion method to the surface of study. And discuss that. If you want.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s