A Java Binary Tree is a non-linear data structure where data objects are organized in terms of hierarchical relationships.
Every value in the tree is a node. The first value 6 has 2 child nodes 4 and 8. 4 and 8 again have 2 child nodes each.
In general, a Binary Tree has no conditions for new insertion but a Binary Search Tree will follow a definite order.
The above example is also a BST(Binary Search Tree).
Here, we shall also take care that every left child of a node is smaller than the node itself and the right child is greater. This later helps in several types of search implementations.
Let’s say we want to find the smallest value in a BST, then we simply move left from the root node(6) until we hit end(node 3).
How easy!
Java Binary Tree Implementation
First, we define a class named TreeNode
for every node in the Tree.
This class will contain the value, the left, right child, and also the parent node.
//defining a TreeNode class with data, parent, left and right child
private class TreeNode{
int data;
TreeNode parent;
TreeNode left;
TreeNode right;
public TreeNode(int data, TreeNode parent) {
this.data = data;
this.parent = parent;
}
public TreeNode() {
// TODO Auto-generated constructor stub
}
}
Now, we must define the necessary functions to work with our Binary Search Tree.
The basic operations are:
- add
- traversal
- delete.
Let’s look at them one at a time.
add:
In this method, we pass a tree node and its parent node and the new value.
- At first, we check if the head is null?
- Then we create a head node.
- Else we compare the new node value with the current node value.
- If the new node value is less than the current node then we make a recursive call with the left node of the current node in line 13.
- Before that, we must make sure that the left node is null.
- Similarly, the right child node is called if the new node is larger than the current node.
void addUtil(TreeNode t, TreeNode parent, int value) {
if (head == null) {
head = new TreeNode(value, parent);
//System.out.println(" "+head.data);
}
else {
if(t.data > value) {
if(t.left == null) {
t.left = new TreeNode(value,t);
return;
}
addUtil(t.left,t,value);
}
else {
if(t.right == null) {
t.right = new TreeNode(value,t);
return;
}
addUtil(t.right,t,value);
}
}
}
traversal:
We can traverse a BST in four primary ways
- InOrder
- PreOrder
- PostOrder
- LevelOrder

Preorder, Postorder, Inorder, Level order traverse a BST in primary ways
InOrder
Here, we make a recursive call to the left child. Then print the current node value and again make a recursive call with the right child.
void inorderUtil(TreeNode t, int i) {
i++;
if(t == null)
return;
inorderUtil(t.left, i);
System.out.print(" "+t.data);
inorderUtil(t.right, i);
if(i == 1)
System.out.println();
}
You can ignore the value i. As its sole purpose is to move to the next line after traversing the tree.
PreOrder
In this traversal, we visit every node and print it first. Then we make two sequential recursive calls with left and right children.
void preorderUtil(TreeNode t, int i) {
i++;
if(t == null)
return;
System.out.print(" "+t.data);
preorderUtil(t.left, i);
preorderUtil(t.right, i);
if(i == 1)
System.out.println();
}
PostOrder
First, we make the recursive calls and then we print the node value in the end.
void postorderUtil(TreeNode t, int i) {
i++;
if(t == null)
return;
postorderUtil(t.left, i);
postorderUtil(t.right, i);
System.out.print(" "+t.data);
if(i == 1)
System.out.println();
}
LevelOrder
We traverse the tree each level at a time. For this one, we also need a maxHeight function to calculate the height of the Binary Tree.
int maxHeight(TreeNode t) {
if(t == null)
return 0;
else {
int lheight = maxHeight(t.left);
int rheight = maxHeight(t.right);
if(lheight > rheight)
return lheight+1;
else
return rheight+1;
}
}
void levelorder() {
System.out.print("levelorder: ");
int height = maxHeight(head);
for(int i = 1; i<=height; i++)
levelorderUtil(head, i);
System.out.println();
}
void levelorderUtil(TreeNode t, int lvl) {
if(t == null)
return;
else if(lvl == 1)
System.out.print(t.data+" ");
else {
levelorderUtil(t.left, lvl-1);
levelorderUtil(t.right, lvl-1);
}
}
delete:
Let’s say we want to delete a Treenode from our tree. We shall face 3 distinct situations, the node to be deleted having –
- no child
- one child
- two child
In the case of no child, we don’t have anything to take care of. We simply delete the required node.
In case 2, for one child, we delete the connection of the node with its parent by establishing a connection between its parent and child.
In the last case, for 2 children, the complexity arises. Here, we search for the maximum in the left sub-tree and update the value of the node to be deleted with it. Then we again call the function to delete the Maximum value in the left-subtree because now our tree has a duplicate of that node in place of the node to be deleted.
void delete(int value) {
if(findNode(head, value)) {
System.out.println("deleted node "+value);
}
else {
System.out.println("node "+value+" not found! ");
}
}
boolean findNode(TreeNode t, int value) {
while(t != null) {
if(t.data > value) {
t = t.left;
}
else if(t.data < value){
t = t.right;
}
else {
//delete
deleteUtil(t,t.parent,value);
return true;
}
}
return false;
}
void deleteUtil(TreeNode t,TreeNode p, int value) {
//2 child
if(t.left != null && t.right != null) {
t.data = findMax(t.left);
deleteUtil(t.left, t, t.data);
}
//no child
else if(t.left == null && t.right == null) {
if(p.left.data == t.data) {
p.left = null;
}
else {
p.right = null;
}
}
//1 child
else {
TreeNode temp = t.left == null ? t.right : t.left;
if(p.left.data == t.data) {
p.left = temp;
}
else {
p.right = temp;
}
}
}
int findMax(TreeNode t) {
if(t.right != null) {
t = t.right;
}
return t.data;
}
Code Java Binary Tree Example
BST.java
public class BST {
TreeNode head;
//defining a TreeNode class with data, parent, left and right child
private class TreeNode{
int data;
TreeNode parent;
TreeNode left;
TreeNode right;
public TreeNode(int data, TreeNode parent) {
this.data = data;
this.parent = parent;
}
}
//insertion of node in BST
void add(int value) {
addUtil(head,null,value);
}
void addUtil(TreeNode t, TreeNode parent, int value) {
if (head == null) {
head = new TreeNode(value, parent);
//System.out.println(" "+head.data);
}
else {
if(t.data > value) {
if(t.left == null) {
t.left = new TreeNode(value,t);
return;
}
addUtil(t.left,t,value);
}
else {
if(t.right == null) {
t.right = new TreeNode(value,t);
return;
}
addUtil(t.right,t,value);
}
}
}
void inorder() {
System.out.print("inorder: ");
inorderUtil(head, 0);
}
void inorderUtil(TreeNode t, int i) {
i++;
if(t == null)
return;
inorderUtil(t.left, i);
System.out.print(" "+t.data);
inorderUtil(t.right, i);
if(i == 1)
System.out.println();
}
void preorder() {
System.out.print("preorder: ");
preorderUtil(head, 0);
}
void preorderUtil(TreeNode t, int i) {
i++;
if(t == null)
return;
System.out.print(" "+t.data);
preorderUtil(t.left, i);
preorderUtil(t.right, i);
if(i == 1)
System.out.println();
}
void postorder() {
System.out.print("postorder: ");
postorderUtil(head, 0);
}
void postorderUtil(TreeNode t, int i) {
i++;
if(t == null)
return;
postorderUtil(t.left, i);
postorderUtil(t.right, i);
System.out.print(" "+t.data);
if(i == 1)
System.out.println();
}
int maxHeight(TreeNode t) {
if(t == null)
return 0;
else {
int lheight = maxHeight(t.left);
int rheight = maxHeight(t.right);
if(lheight > rheight)
return lheight+1;
else
return rheight+1;
}
}
void levelorder() {
System.out.print("levelorder: ");
int height = maxHeight(head);
for(int i = 1; i<=height; i++) levelorderUtil(head, i); System.out.println(); } void levelorderUtil(TreeNode t, int lvl) { if(t == null) return; else if(lvl == 1) System.out.print(t.data+" "); else { levelorderUtil(t.left, lvl-1); levelorderUtil(t.right, lvl-1); } } void print() { printUtil(head, 0, 0); } void printUtil(TreeNode t, int c, int lvl) {//left -> -1 right -> 1
int shift = 20;
if(t == null) {
return;
}
for(int i = 0; i<c+shift; i++) { System.out.print(" "); } System.out.println(t.data); lvl += 2; printUtil(t.left, c-10+(lvl), lvl); printUtil(t.right, c+10-(lvl), lvl); } void delete(int value) { if(findNode(head, value)) { System.out.println("deleted node "+value); } else { System.out.println("node "+value+" not found! "); } } boolean findNode(TreeNode t, int value) { while(t != null) { if(t.data > value) {
t = t.left;
}
else if(t.data < value){
t = t.right;
}
else {
//delete
deleteUtil(t,t.parent,value);
return true;
}
}
return false;
}
void deleteUtil(TreeNode t,TreeNode p, int value) {
//2 child
if(t.left != null && t.right != null) {
t.data = findMax(t.left);
deleteUtil(t.left, t, t.data);
}
//no child
else if(t.left == null && t.right == null) {
if(p.left.data == t.data) {
p.left = null;
}
else {
p.right = null;
}
}
//1 child
else {
TreeNode temp = t.left == null ? t.right : t.left;
if(p.left.data == t.data) {
p.left = temp;
}
else {
p.right = temp;
}
}
}
int findMax(TreeNode t) {
if(t.right != null) {
t = t.right;
}
return t.data;
}
}
testTree.java
public class testTree {
public static void main(String[] args) {
BST t = new BST();
t.add(3);
t.add(4);
t.add(1);
t.add(0);
t.add(2);
t.add(6);
t.add(7);
t.add(5);
t.inorder();
t.preorder();
t.postorder();
t.levelorder();
t.print();
t.delete(4);
t.print();
}
}
OUTPUT
Java Tree Library
Java also provides tree-based data structure implementations for us to use:
- TreeSet
- TreeMap
TreeSet
TreeSet is one of the most important implementations of the SortedSet interface in Java that uses a Tree for storage. The ordering of the elements is maintained by a set using their natural ordering. It can also be ordered by a Comparator provided at set creation time, depending on which constructor is used. The TreeSet implements a NavigableSet interface by inheriting AbstractSet class.
import java.util.*;
class TreeSetExample {
public static void main(String[] args)
{
TreeSet ts1 = new TreeSet();
// Elements are added using add() method
ts1.add("A");
ts1.add("B");
ts1.add("C");
// Duplicates will not get insert
ts1.add("C");
// Elements get stored in default natural
// Sorting Order(Ascending)
System.out.println(ts1);
}
}
TreeMap
Java TreeMap class is a red-black tree-based implementation. It provides an efficient means of storing key-value pairs in sorted order.
The important points about the Java TreeMap class are:
- Java TreeMap contains values based on the key. It implements the NavigableMap interface and extends AbstractMap class.
- Contains only unique elements.
- Java TreeMap cannot have a null key but can have multiple null values.
- Java TreeMap is non synchronized.
- Maintains an ascending order.
OUTPUT
import java.util.*;
class TreeMapExample{
public static void main(String args[]){
TreeMap<Integer,String> map=new TreeMap<Integer,String>();
map.put(100,"Amit");
map.put(102,"Ravi");
map.put(101,"Vijay");
map.put(103,"Rahul");
for(Map.Entry m:map.entrySet()){
System.out.println(m.getKey()+" "+m.getValue());
}
}
}
OUTPUT
We hope this tutorial helped you to achieve the same. Keep learning keep sharing. Follow us on Facebook and Instagram. Also, if you need any Java homework help or Java coding help, feel free to contact us.
What a fantastic article on binary search tree and when I contacted them about a small doubt their response was outstanding. They did share YouTube like as well for better understanding of this concept : https://www.youtube.com/watch?v=76n3fiQfwtw .
We love to do programming and help students all around the globe. Thanks!! Pacioli 🙂
I can definitely see your skills in the article you write. This definitely helped me in my studies and I have subscribed your RSS feeds so that I can get regular updates.
Thank you for subscribing to our RSS feeds.
Very easy and genuinely a good piece of writing, keep it up.
Thanks!
Thank you for the Feedback, Emile! The team here is thrilled to hear such good feedback.