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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | package com.techielogic; /** * @author Praveen * */ public class Node { int value; Node left; Node right; public Node(int value) { this.value= value; this.left=null; this.right=null; } } |

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 | package com.techielogic; /** * @author Praveen * */ public class MyBST { Node root; public MyBST() { root = null; } } |

**getRoot():**

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

1 2 3 | public Node getRoot() { return root; } |

**isEmpty():**

1 2 3 | public boolean isEmpty() { return root == null; } |

**add():**

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | public void add(int value) { root = addRecursive(root, value); } private Node addRecursive(Node current, int value) { if (current == null) { System.out.println("adding node with Value :" +value); return new Node(value); } if (value < current.value) { System.out.println("Current node is left"); current.left = addRecursive(current.left, value); } else if (value > current.value) { System.out.println("Current node is right "); current.right = addRecursive(current.right, value); } else { return current; } return current; } |

**delete():**

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | public void delete(int value) { root = deleteRecursive(root, value); } private Node deleteRecursive(Node current, int value) { if (current == null) return null; if (current.value > value) { current.left = deleteRecursive(current.left, value); } else if (current.value < value) { current.right = deleteRecursive(current.right, value); } else { // if nodeToBeDeleted have both children if (current.left != null && current.right != null) { Node temp = current; // Finding minimum element from right Node minNodeForRight = minimumElement(temp.right); // Replacing current node with minimum node from right subtree current.value = minNodeForRight.value; // Deleting minimum node from right now deleteRecursive(current.right, minNodeForRight.value); } // if nodeToBeDeleted has only left child else if (current.left != null) { current = current.left; } // if nodeToBeDeleted has only right child else if (current.right != null) { current = current.right; } // if nodeToBeDeleted do not have child (Leaf node) else current = null; } return current; } public Node minimumElement(Node root) { if (root.left == null) return root; else { return minimumElement(root.left); } } |

Let’s create main method test all the functionality.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | package com.techielogic; public class APP { public static void main(String[] args) { MyBST myBST = new MyBST(); System.out.println(myBST.isEmpty()); myBST.add(100); myBST.add(25); myBST.add(45); myBST.add(200); myBST.add(65); myBST.add(75); myBST.delete(200); System.out.println(myBST.getRoot().value); } } |

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.