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

1. Objective

In Part 1 – Linear Data Structures in Java, we discussed arrays, linked lists, stacks, and queues. In this Java tutorial, we are going to study about Hierarchical Data Structure: Binary Tree, BST, Heap, and Hash in detail with examples.

So, let us start with Hierarchical Data Structure in Java.

Hierarchical Data Structure in java

Hierarchical Data Structure in java

2. Hierarchical Data Structure in Java

In this Java tutorial, we are going to study the Types of Java hierarchical data structure–

  • Binary Tree
  • Binary Search Tree
  • Heap
  • Hash

Do you know What is Java HashMap?

3. Binary Tree

A hierarchical data structure in java is unlike linear data structures, a binary tree is a tree data structure, it can have at most two children, called the left child and the right child, and it is implemented using links.

Introduction – Binary Tree and Binary Search Tree

a. Representation of Binary Tree

A binary tree is represented by a pointer on the topmost node in a tree, if the nodes in the tree are empty then the root of that tree is NULL.

Following are the parts of a tree –

  • Data
  • Pointer to the right child
  • Pointer for the left child

Let’s Test Your Knowledge – Java Quiz Questions

A binary tree can be traversed in the following two ways –

  •  Depth

In order (Left-Root-Right), Preorder (Root-Left-Right) and Postorder (Left-Right-Root)

  • Breadth

Level Order Traversal

b. Properties of Binary Tree

The most number of nodes at level ‘l’2^(l-1)
Maximum number of nodes ( h is height of tree)2^(h – 1)
Minimum possible height ()log with base 2)ceil(Log(n+1))
Time Complexity of Tree Traversal0(n)

c. Binary Tree Example

One motivation to utilize binary tree or tree, as a rule, is for the things that shape a chain of command. They are valuable in File structures where each record is situated in a specific index and there is a particular order related to documents and catalogs. Another illustration where Trees are valuable is putting away hierarchical objects like JavaScript Document Object Model considers HTML page as a tree with settling of labels as parent tyke relations.

4. Binary Search Tree (BST)

Binary search Tree is another Hierarchical data structure in Java, which is similar to a binary tree but with some added properties, they are –

  • The left subtree of the BST has nodes which are less than the node’s key.
  • Left subtree of the BST has only nodes with keys greater than the node’s key.
  • Left and right should also be BST.

They provide quicker access and search options which is quicker than linked lists and slower than arrays.

Read about Java Regular expression & Inheritance in Java 

They provide quicker insertion and deletion options which is quicker than arrays and slower than linked lists.

a. Time Complexities

Search: O(h)

Insertion: O(h)

Deletion: O(h)

Extra Space: O(n) for pointers

h: Height of BST

n: Number of nodes in BST

If Binary Search Tree is Height Balanced,

h = O(log n)

Let’s Learn JRE (Java Runtime Environment) With Example

Example –

Its fundamental utilize is in look application where information is continually entering/leaving and information needs to imprinted in an arranged request. For instance in usage in E-business sites where another item is included or item leaves stock and all items are listed in the arranged request.

5. Binary Heap

A binary heap is a binary tree of a Hierarchical data structure in Java with added facilities –

  • It’s an entire tree (All levels are totally filled aside from potentially the last level and the last level has all keys as left as could expect under the circumstances). This property of Binary Heap makes them appropriate to put away in an exhibit.
  • Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be least among all keys show in Binary Heap. A similar property must be recursively valid for all hubs in Binary Tree. Max Binary Heap is like MinHeap. It is, for the most part, actualized utilizing exhibit.

Get Minimum in Min Heap: O(1) [Or Get Max in Max Heap]

Extract Minimum Min Heap: O(Log n) [Or Extract Max in Max Heap]

Decrease Key in Min Heap: O(Log n)  [Or Extract Max in Max Heap]

Insert: O(Log n)

Delete: O(Log n)

Example –

Utilized as a part of actualizing productive need lines, which thusly utilize for planning forms in working frameworks. Need Queues are likewise utilized as a part of Dijstra’s and Prim’s diagram calculations.

Request measurements: The Heap information structure can utilize to productively discover the k’th littlest (or biggest) component in an exhibit.

Heap is an extraordinary information structure and it can’t utilize for seeking a specific component.

Read about Java Exception HandlingPolymorphism in Java with Example

6. HashingHash Function

A hashingHash function – Hierarchical data structure in java use to convert a big input key to a small integer value which is more practical.

  • Collision Handling: Since a hash work gets us a modest number for a key which is a major whole number or string, there is plausibility that two keys result in the same value. The circumstance where a recently embedded keymap to an effectively possessed space in a hash table is called impact and should take care of utilizing some crash taking care of procedure.

Following are the approaches to deal with it:

Chaining: The thought is to make every cell of hash table point to a connected rundown of records that have same hash work esteem. Chaining is basic, yet requires extra memory outside the table.

Open Addressing: In open tending to, all components are put away in the hash table itself. Each table section contains either a record or NIL. While hunting down a component, we one by one look at tablespaces until the point when the coveted component is found or unmistakably the component isn’t on the table.

Space: O(n)

Search: O(1) [Average] O(n) [Worst case]

Insertion: O(1) [Average] O(n) [Worst Case]

Deletion: O(1) [Average] O(n) [Worst Case]

So, this was all about Hierarchical Data Structure in Java. Hope you like our explanation.

7. Conclusion

In this tutorial, we learned about the second set of a Hierarchical data structure in Java programming language, in the second set we covered Binary Tree, Representation of Binary Tree, Properties of Binary Tree, Binary Search Tree, Binary Heap, HashingHash Function. In the third set, we will cover graphs and other topics. Furthermore, if you have any query, feel free to ask in the comment section.

See Also- Serialization and Deserialization in Java 

For reference

1 Response

  1. Veena says:

    in explanantion of 4. Binary Search Tree (BST), the second point is incorrect.
    It should be:
    Right subtree of the BST has only nodes with keys greater than the node’s key.

Leave a Reply

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