Binary Search Tree Implementation Java

In this topic, We are going to Learn the basics of a binary tree and Binary Search Tree Implementation Java.

A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as “left” and “right” node.

Binary search tree has the following properties.

  • It should not have duplicate nodes.
  • Always left subnode will be smaller than root.
  • Always right subnode will be greater than root.
  • Both the left and right subtree also should be a binary search tree.

Advantages of using a binary search tree

  • The binary search tree is considered an efficient data structure in compare to arrays and linked lists for searching. In the searching process, it removes half sub-tree at every step. Searching for an element in a binary search tree takes o(log2n) time. In the worst case, the time it takes to search an element is 0(n).
  • It also speeds up the insertion and deletion operations as compared to that in the array and linked list.

Binary Search Tree Implementation Java:

Here I am going explain how to create binary search tree implementation in java and also some basic methods such as.

  • getRoot() : returns the root of the binary tree
  •  isEmpty(): to check if a binary search tree is empty or not
  • add(): Adding new node.
  • delete(): delete specific node.

As part of this, we are using int instead of generics.

Node:

Create a Node class that will store int values and keeps a reference to each child:

As we can see in the above code every node represent int value along with containing the reference of both auxiliary Nodes.

Let’s create your own custom BST and add root node in class.

getRoot():

getRoot () function will return the root node of the Binary tree.

isEmpty(): 

 

add():

add() function is used inserting the new node to the binary tree. We are using recursive to inserting the node.

delete():

delete() function is used delete the specific node in the binary tree. Here also we are using recursion to delete the node.

Let’s create main method test all the functionality.

In this tutorial, We have learned to create the structure of BST using Node class and some basic function of BST. In the upcoming article, We will discuss more on data structures.

Leave a Reply

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

Show Buttons
Hide Buttons