# Tree Implementation in Java

In this article, we will provide a custom implementation of Tree data structure in Java. We will discuss a special case of Tree, i.e.- Binary Search Tree(BST). We will perform multiple tree operations such as insert(), findMin(), findMax() and search() in a BST using Java.

The below tree implementation will be based on the linked list implementation. You can check out linked list implementation in Java here.

## What is Tree

Tree is a non-linear data structure for representing the hierarchical data structure in a graphical form. It is similar to a linked list but instead of each node pointing simply to the next node in a linear fashion, each node points to a number of nodes.

## What is Binary Search Tree

As we know, a binary tree is a special tree in which each node has zero child, one child or two children. Empty tree is also a valid binary tree. Now, Binary Search Tree(BST) is another variant of binary tree which is mainly used for searching. BST reduces the worst-case average search operations to O(logn).

### BST Properties

- The left subtree of a node should contain only nodes with keys less than the nodes key.
- The right subtree of a node contains only nodes with keys greater than the nodes key.
- Both the left and right subtrees must be binary search trees.

**Since, root data is always between left subtree data and right subtree data, performing inorder traversal on binary search tree produces a sorted list.**

## BST Node Implementation

As discussed above, each node of a BST tree can point to a max of 2 children. Hence, below is the declaration of a BST.

public class BSTNode { private int data; private BSTNode left; private BSTNode right; public BSTNode(int data){ this.data = data; } //setters and getters }

## BST Insertions

All BST operations are recursive. The first insertion is the root node of a BST. Then based on the data, we perform recursive insert operations either in the left or right subtree. If the data to be inserted is less than node data then insert the data in the left subtree otherwise the data is inserted in the right subtree.

public BSTNode insert(BSTNode node, int data) { if(node == null) { node = new BSTNode(data); }else { if(data < node.getData()){ node.setLeft(insert(node.getLeft(), data)); }else if(data > node.getData()){ node.setRight(insert(node.getRight(), data)); } } return node; }

## BST Search

Start with the root and keep moving left or right based on the data that is either less than or greater than the node data recursively.

public BSTNode search(BSTNode root, int data){ if(root == null){ return null; } while (root != null){ if(data == root.getData()){ return root; }else if(data > root.getData()){ root = root.getRight(); }else { root = root.getLeft(); } } return null; }

## BST Find Smallest Element

As per the BST property, the smallest element of a BST is the left-most node, which does not has the left child.

public BSTNode findMin(BSTNode root){ if(root == null){ return null; } while (root.getLeft() != null){ root = root.getLeft(); } return root; }

## BST Find Largest Element

In BSTs, the maximum element is the right-most node, which does not have right child.

public BSTNode findMax(BSTNode root){ if(root == null){ return null; } while (root.getRight() != null){ root = root.getRight(); } return root; }

## Full Balanced Binary Search Tree

Full balanced BST is a BST in which the difference between left subtree height and right subtree height is at most zero. This ensures that the tree is a full binary tree.

## AVL(Adelson-Velskii and Landis) Tree

An AVL tree is a binary search tree with a balanced condition: the difference between left subtree height and right subtree height is at most 1.

## Conclusion

In this article, we provided a custom implementation of BST in Java performed multiple tree operations such as insert(), findMin(), findMax() and search().

#### If You Appreciate This, You Can Consider:

#### About The Author

A technology savvy professional with an exceptional capacity to analyze, solve problems and multi-task. Technical expertise in highly scalable distributed systems, self-healing systems, and service-oriented architecture. Technical Skills: Java/J2EE, Spring, Hibernate, Reactive Programming, Microservices, Hystrix, Rest APIs, Java 8, Kafka, Kibana, Elasticsearch, etc.

### Recommended

- Graph Implementation Java
- Linkedlist Implementation Java
- Queue Implementation Java
- Stack Implementation Java
- Pros And Cons Collection Java
- Hashmap Custom Implementation Java
- Different Sorting Algorithms
- Doubly Linked List Implementation
- Blocking Queue Implementation In Java
- Dijkstra Algorithm Java