Binary Tree

Binary Tree

Definition

Binary tree is a non-linear data structure that is composed of two nodes at most. This is where its name comes from. However, it is not necessarily for a Binary Tree to have maximum two nodes. However, it can be even zero. Furthermore, there is also an implementation of Binary Tree called “Binary Search Tree(a.k.a ordered binary tree)” that preserves data in a sorted fashion. From this point on, we will be talking and focusing on Binary Search Tree. To sum up the characteristics of a Binary Search Tree

  • Compared to the root key, greater key goes to the right, less goes to the left,
  • There are two ways of traversals (breadth first and depth first) compared to one-dimensional arrays and linked lists. This topic is in detailed explained in the following chapters,
  • Average cases of Positional Access, Search, Insertion and Deletion operations are far faster in tree that is denoted as O(log N) in the Big O Notation. This will also be covered in the following chapter.

The full source code of the Binary Tree and the test cases can be obtained from my public GitHub repository. There will be more utility methods and test cases covering the chapter.

https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures

During my research, I have found out a very useful visualized Binary Tree application that you can see interactively how it works out https://www.cs.usfca.edu/~galles/visualization/BST.html

Let’s look into the source code how we can create a Binary Tree.

Node.java

public class Node {
    Node leftNode;
    Node rightNode;
    int key;

    Node(int key) {
        this.key = key;
    }
}

BinaryTree.java

public class BinaryTree {

    private Node rootNode;
    private final static int DATA_NOT_AVAILABLE = -1;

//The rest of the code can be obtained on GitHub
}

BinaryTree.java file contains all the operations and very long to share the details here, please refer to GitHub for the full source that is available.

Glossary and Properties

Before diving into Binary Search Tree, we will need to have a ubiquitous language to apprehend all the terms used in this data structure.

Binary Tree Glossary

Root: The only top most element that has no other nodes above it,

Node: Every member in the tree is known as Node including the root as well,

Parent Node: The node that has two children,

Child Node: A node that is associated with a parent node

Leaf: A leaf is a node that does not have any children,

Path/Edge: The lines that bind all available nodes,

Subtree: It is a triangle shape in a tree. Essentially a parent with its two child nodes,

Height: The height of a tree is the number of the edges from the Root node to its deepest leaf.

Some Binary Tree Height Samples as follow:

Binary Tree Glossary Height is three

Binary Tree Glossary height is four

Performance of Binary Tree

The Big O Notation measures the performance of data structures and algorithms. In the notation we will have Time Complexity that represents how the code how fast and slow operations carry out the actions as well as the space complexity that points out how much of space will be consumed. In the below time the Performance of the Binary Search Tree is demonstrated.

Binary Tree Big O Notation
Image courtesy: www.bigocheatsheet.com

Types of Binary Trees

In this post, I will restrict to represent only four types of Binary Trees. Because there are other types that are very in depth. Types of tree are made in a way of the nodes are inserted.

Balanced Tree

Balanced and Unbalanced Trees

 

A Balanced Tree is composed when there is a balance between right and left nodes, but at most one side differs only by one node, otherwise it will be considered as an Unbalanced Tree. The operations in a balanced tree are performed in O(log n) notation.
In Addition, Balanced Tree Type has other implementations such as AVL, Red-Black, Weight and Height Balanced Trees etc. It is a good practice to apprehend the definition of the balanced tree.

Unbalanced Tree

Unbalanced Tree

Ordered data sets make up the unbalanced tree. In this type, most of the nodes are located on one side of the tree. In Unbalanced Trees, we cannot favor of fast operations denoted as O(log n), it is actually O(n) in this type.

Full Binary Tree

Full Binary Tree

Full Binary Tree is a tree type that consists of a situation where leaves have zero or nodes have two children.

Complete Tree

Complete Binary Tree

Complete Tree is a type of a Binary Tree in which;

  1. Each left and right node child,
  2. Exceptionally the last level has left justified extra nodes

Tree Traversal

Traversal also the acronym known as Tree Search is a type of an action that leads to visiting every single node in the tree and performing selection, insertion, updating and deletion. While going/traversing through there are number of ways to do so namely; Breadth First and Depth First traversals.

Tree Traversal

Breadth First Traversal

Breadth First Tree Traversal

Breadth First Traversal traverses the tree in a level fashion. It internally utilizes a queue, to visit nodes in layers as you can see the illustration. The algorithm of Breadth First Traversal goes;

public void breadthFirstTraversal() {
        if (rootNode == null)
            return;
        System.out.printf("***Breadth First Traversal***\n");
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(rootNode);
        while (!queue.isEmpty()) {
            rootNode = queue.remove();
            System.out.println(rootNode.key);
            if (rootNode.leftNode != null)
                queue.add(rootNode.leftNode);
            if (rootNode.rightNode != null)
                queue.add(rootNode.rightNode);
        }
}

Console Output:

***Breadth First Traversal***
60
55
67
50
57
61
77
45
53

Depth First Traversal

Deep First travel is slightly different and more complicated compared to the Breadth first traversal. We would assume it as the exact opposite of it as well as minding that there are three ways of implementing it, while the sub chapter of Deep First Traversal explains each of them. Basically, we practice the Depth first traversal, we will visit each node and leaf, not minding the layers, but the Depth itself.

In Order Traversal

In Order Traversal

In Order Traversal has the following sequence:

  1. Left Node,
  2. Root Node,
  3. Right Node

Having said that when the traversal begins, it starts from the deepest left node. As the second item goes to the root, it is not the top root but the parent root. Then it follows the right node. As you see the above illustration, the algorithm starts in “45” the deepest left node and ends in “77” the highest right node in the tree. Observe the code for traversal:

private void inOrderTraversal(Node node) {

        if (node != null) {

            inOrderTraversal(node.leftNode);

            System.out.println(node.key);

            inOrderTraversal(node.rightNode);

        }

    }

Console Output:

***In Order Traversal***
45
50
53
55
57
60
61
67
77

Pre Order Traversal

Pre Order Traversal

Pre Order Traversal has the following sequence:

  1. Root Node,
  2. Left Node,
  3. Right Node

Having said that when the traversal begins, it starts from the root node. As the second item goes to the next left root. Then here the algorithm starts to visit the left and accordingly the right node. As you see the above illustration, the algorithm starts in “60” the root node and ends in “77” the highest right node in the tree. Observe the code for traversal:

private void preOrderTraversal(Node node) {

        if (node != null) {

            System.out.println(node.key);

            preOrderTraversal(node.leftNode);

            preOrderTraversal(node.rightNode);

        }

    }

Console Output:

***Pre Order Traversal***
60
55
50
45
53
57
67
61
77

Post Order Traversal

Post Order Traversal

Post Order Traversal has the following sequence:

  1. Left Node,
  2. Right Node,
  3. Root Node

Having said that when the traversal begins, it starts from the deepest left node. As the second item goes to the next right node. Last of all it visits the root node of the children. As you see the above illustration, the algorithm starts in “45” the deepest left node and ends in “60” the root node. Observe the code for traversal:

private void postOrderTraversal(Node node) {

        if (node != null) {

            postOrderTraversal(node.leftNode);

            postOrderTraversal(node.rightNode);

            System.out.println(node.key);

        }

    }

Console Output:

***Post Order Traversal***
45
53
50
57
55
61
77
67
60

Leave a Reply

Your email address will not be published. Required fields are marked *