Hierarchical Data Structure in Java – Binary Tree, Binary Search Tree, Heap, Hash

Before we start, as usual, we would look at an example of a hierarchical data structure in real life.

Let us take the example of your family. Let’s say your great grandfather had two children, a girl and a boy. Each of these two children had three children each. Again, each of these three children have two children each. If you try to represent these by linear data structures you would face a lot of problems. Keep in mind that although it is not impossible to represent them in a linear fashion, it is quite difficult.

Hence we use a tree-like structure starting with your grandfather and ending with you. After drawing this, it will be easier for you to understand the family tree. In programming, these types of data structures are Hierarchical Data Structure. Let us learn more about them.

Hierarchical Data Structure in Java

As we already know, linear data structures store data in a linear fashion. Similarly, hierarchical data structures store elements on the basis of hierarchy. This is efficient for visualizing and retrieving data.

Some of the popular hierarchical data structure in Java are

• Binary Tree
• Binary Search tree
• Heap
• Hash

Binary Tree

Take the example we talked about in the introduction of this article. Now let’s say your grandfather had two children. And each of his children had two children each. In this manner, if every individual has at most two children, then the resulting tree would be a binary tree.

A binary tree has the following properties:

• There can only be two child nodes of a single node, except the leaf nodes.
• A leaf node does not have any children.
• Each node has a field to store data, i.e, the value of the node.
• Each node has a pointer to the left child node and a pointer to the right child node.
• At a level ‘l’ there can be a maximum of 2^(l-1) nodes.
• If ‘h’ is the height of the tree, then the maximum number of nodes in the tree are 2^(h-1)
• The time taken to traverse a Binary Tree would be O(n).
• The minimum possible height of a binary tree would be ceil(log(n+1)) where n is the number of nodes and the log is of base 2.

Types of Binary tree in java

There are 5 types of binary trees:

1. Full Binary Tree in Java

You can call a binary tree, a full binary tree, when each of its nodes contain exactly 2 children or none at all. There can be no node having a single child or more than two children. It is a tree where each node has two children except the leaf nodes. There are a total of internal nodes+1 leaf nodes in a binary tree.

LeafNodes=InternalNodes+1.

2. Complete Binary Tree in Java

A complete binary tree has all of its levels filled except the last level. What do we mean by filled? Well, a level “filled” if it has 2^L nodes where L is the level. L starts from 0. Hence the first level(0th level ) has 2^0=1 Node, the second level has 2^1 nodes, i.e, 2 nodes, so on.

The keys or the nodes in the last level are as left-oriented as possible.

Binary Heaps are complete Binary Trees. We will read about them in detail later in this article.

3. Perfect Binary Tree in Java

A binary tree is deemed as being a perfect binary tree when each level is complete( this means that each node has exactly 2 child nodes). A perfect Binary tree also has all of its leaf nodes at the same level. The number of nodes in a perfect binary tree is 2^h-1, where “h” is the height of the tree.

4. Balanced Binary Tree in Java

A balanced binary tree is a tree where the height of a tree is an exact power of 2. You can think of it as a tree where the height of a tree is log(n), where n is the number of nodes. There are many trees that follow this concept.

AVL Trees are balanced trees. They make sure that the difference between the heights of the left and right subtrees is almost equal to 1.
Balanced Binary Trees implement this concept. This is why they provide optimized time complexities for search insert and delete operations on the tree.

5. Pathological or Degenerate Trees in Java

Pathological Trees are the trees where each node has only one child. The tree does not live up to its name because this is very similar to Linked Lists.

Applications of Binary Tree in Java

• Binary trees are particularly useful for storing data where data is extremely dynamic in nature, i.e, data is constantly added and removed.
• All routers including the one in your home use Binary Trees for storing the routing tables
• Wireless networking also sees a lot of Binary Tree usage these days.
• Many compression algorithms also use Binary Trees.

Binary Search Tree in Java

Binary Search Tree(BST) is very similar to Binary Trees, but there is a catch. Each and every node only contains elements lesser than itself on the left side and elements greater than itself on the right side.

• The left subtree of a particular node contains elements that are smaller in value than the current node.
• The right subtree of a particular node contains elements that are greater than the value of the current node.
• Do note that the left and right subtrees of the current node should also be a Binary Search Tree.
• BST’s allow faster searching than arrays.
• They also provide quicker insertion and deletion operations.

Time Complexities of BST in Java

1. Searching takes O(h) where h is the height of the tree.
2. Insertion takes O(h).
3. In order to delete a node, the complexity is O(h)
4. It takes linear space, i.e, O(n) for pointers to the adjacent nodes.
5. If the number of nodes in a binary search tree is n then the height of the binary tree is O(log(n)) if it is a balanced tree.

Binary Heap in Java

You can think of a binary heap as being very similar to a binary tree with a few differences. Let us look at them

• Binary heaps are complete binary trees. We read about complete binary trees in the previous topic. All of their levels are complete except the last level. However, their last level has all of its nodes as left-oriented as possible. You can store binary heap as an array or any collection because of this property.
• Binary Heaps are either MinHeaps or MaxHeaps. A MinHeap is a data structure that has the least element as the root of the tree. This same condition should be recursively true for the remaining subtrees. A Maxheap is simply the opposite of a MinHeap. Its root has the maximum element. This is also true for all the remaining subtrees.
• Binary heaps are useful for implementing priority queues and heap sort.
• Graph Algorithms such as Dijkstra’s Shortest path and Prim’s Algorithm can be efficiently implemented by Binary heaps.
• You can also use Binary heaps for finding the Kth smallest or largest value in a collection.

Applications of Binary Heaps in Java

Binary heaps in Java are popularly used in implementing Heap data structures, priority queues, and in problems where the kth smallest or largest elements need to be found efficiently. Binary heaps reduce the time complexity of these problems to a great extent.

Hashing in Java

In layman’s terms, hashing is a simple method for converting large data to a smaller one. This is useful because hashing provides a way for mapping keys to values. They also support efficient lookup times as each key gets mapped to a single value.

A hashing function is a special function that takes an input and then maps it to a value. One popular data structure that implements hashing is a Hash Table. It contains two parts

1. A bucket array – This is responsible for containing the key-value pairs.
2. A hashing function – This converts the objects into hash values.

You cannot invert the hash function to get the original key back although there are some modified hash data structures that allow that. There may be cases where two different inputs, upon hashing, return the same result. This results in errors. There are two ways of working around this error.

• Chaining – Chaining is basically attaching the same result of two different inputs to the hash function together by a chain. For example, if the hash value of ‘a’ is 12H34 and ‘b’ is also 12H34 then both of these results are chained together. This method requires extra space.
• Open Addressing – This method is space-efficient. In this, we put the inputs directly into the hashtable. This means that the result table is equal to or greater than the number of keys. Now while inserting, we keep probing the table until we find an empty, and then we put the element there. For search, we keep on checking every memory slot till we find “k” or we reach an empty slot. While deleting, we place a “deleted” marker on the slot to mark that it has been deleted. If we delete the key only, then a request for search operation may fail. You can implement open addressing by Linear probing, Quadratic Probing, Clustering, and Double Hashing.

Summary

In this article, we learned about hierarchical data structure such as Binary trees, Heaps, Binary Search Trees, and Hashing. We also learned about the various operations that they support. Hierarchical Data Structures is a favorite topic for interviewers to test the candidates upon. It is also very useful for developers who are developing efficient software. So a good concept of these data structures will come in handy.