Binary Tree

First thing is first, we need to understand what a Binary Tree is. There are other various of trees such as Binary Search Tree and AVL Tree which is named after the inventor Adelson-Velskii and Landis but we will look into that at a later date.

However, in this post, we are going to look at Binary Tree and understand how this data structure works and how we can use it by implementing in Java. We will also look at the worst-case time complexity for operations such as access/search/insertion/deletion.  Towards the end, we will create an example and I will provide you with sample code on how this can be implemented.

What is a Binary Tree?

So first things first, what is a Binary Tree? As you might think a tree is a hierarchical structure consisting of nodes. As you might think its the same a normal tree in real life. See figure1  an example of a Binary Tree.

A basic Binary Tree
Figure1

Tree Terminology

Have a look at figure2 below to get an understanding of each part of the tree and what they represent.

 

 

 

 

 

 

 

 

Trees are acyclic. This means there are no cycles, i.e. there are no nodes pointing backwards in the tree. The height of a tree is the length of the longest path from the root to the leaf node. So the height in the above example is 4. The depth of a given node is the length of the path from the root to that node, e.g. the depth of B is 2.

A Binary Tree can only be a true Binary Tree where each node has either 0, 1 or 2 children.

Traversing A Binary Tree

There are 2 algorithms of traversing a Binary Tree. We will have a brief overview at each of them and we will also be implementing them in our implementation at the end of the post.

Breadth-First Search

A basic Binary Tree

A breadth-first search visits the nodes in the order of each level. If we use the same tree from figure1 as an example. The breadth-first search for that tree is 2,7,5,2,6,9,5,11,4

Depth-First Search

A depth-first search travels recursively (if you do not know what this is keep posted for future posts) down to the leaves and then back up.

A depth-first search can be either:

Pre-Order: Visit the root and then the sub-trees, e.g. Using the tree above the results for a pre-order search is 2,7,2,6,5,11,5,9,4
Post-Order: Visit the sub-trees and then the root. e.g. Using the tree above the results for a post-order search is 2,5,11,6,7,4,9,5,2
In-Order: This is usually for Binary Trees where there are two sub-trees. Visit the left sub-tree, then the root and then the sub-right tree. 2,7,5,6,11,2,5,4,9

Worst-Case Time Complexity

We will take a look at the time worst-case time complexity or otherwise known as Big-O notation.

Access – O(log n)
Search – O(log n)
Insertion – O(log n)
Deletion – O(log n)

Implementing A Binary Tree

package lib;

public class Node {
    private Node left, right;
    private int data;

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

    public void insert(int value) {
        if(value <= data) {
            if(left != null) {
                left = new Node(value);
            } else {
                left.insert(value);
            }
        } else {
            if(right != null) {
                right = new Node(value);
            } else {
                right.insert(value);
            }
        }
    }

    public boolean contains(int value) {
        if(value == data) {
            return true;
        } else if (value < data) {
            if(left == null) {
                return false;
            } else {
                return left.contains(value);
            }
        } else {
            if(right == null) {
                return false;
            } else {
                return right. contains(value);
            }
        }
    }


    public void printInOrder() {
        if(left != null) {
            left.printInOrder();
        }
        System.out.println(data);
        if(right != null) {
            right.printInOrder();
        }
    }

    public void printPreOrder() {
        System.out.println(data);
        if(left != null) {
            left.printInOrder();
        }
        if(right != null) {
            right.printInOrder();
        }
    }

    public void printPostOrder() {
        if(left != null) {
            left.printInOrder();
        }
        if(right != null) {
            right.printInOrder();
        }
        System.out.println(data);
    }

}

 

Leave a Comment