In this post we’ll see an implementation of binary tree in Java. Operations covered in this post are-
- Inserting a node in binary tree
- Find a node in binary tree
- Binary tree traversal
- Binary Search tree Java implementation- Full Program
Since deletion of a node from binary search tree is a complex operation having many scenarios so it is taken up as a separate post- Java Program to Delete a Node From Binary Search Tree (BST)
Binary tree data structure
A binary tree is a tree where each node can have at most two children. So a node in binary tree can have only a left child, or a right child, or both or it can have no children which makes it a leaf node.
Binary tree data structure gives the best of both linked list and an ordered array. You can insert and delete nodes fast as in linked list and search a node fast as in an ordered array.
Binary Search tree
Implementation shown here is actually a binary search tree which is a kind of binary tree. In Binary search tree for each node the node’s left child must have a value less than its parent node and the node’s right child must have a value greater than or equal to its parent. If we consider the root node of the binary search tree the left subtree must have nodes with values less than the root node and the right subtree must have nodes with values greater than the root node.
Binary Search tree implementation in Java
To represent each node in the binary search tree a node class is used which apart from data also has two references for left and right child.
class Node{
int value;
Node left;
Node right;
Node(int value){
this.value = value;
left = null;
right = null;
}
}
In the Binary tree implementation class in Java apart from the methods for insertion, traversal and search there is a single field of type Node that holds the root.
class BinaryTree{
Node root;
...
}
Inserting node in a Binary Search tree
When a new node is inserted in a binary search tree you need to find the location to insert the new node. Start from the root and compare the value of the root node with the value of the new node. You need to go to the left child if value is less than the root node value otherwise you need to go to the right child. This traversal is followed until you encounter null that’s the location where new node has to be inserted.
Binary tree insertion Java program can be written as both-
Binary tree insertion Java program – Iterative
public void insert(int i){
Node newNode = new Node(i);
if(root == null){
root = newNode;
}else{
Node current = root;
Node parent;
while(true){
parent = current;
if(i < current.value){
current = current.left;
if(current == null){
parent.left = newNode;
return;
}
}else{
current = current.right;
if(current == null){
parent.right = newNode;
return;
}
}
}
}
}
Binary tree insertion Java program – Recursive
public Node insert(Node node, int value){
if(node == null){
return new Node(value);
}
// Move to the left if passed value is
// less than the current node
if(value < node.value){
node.left = insert(node.left, value);
}
// Move to the right if passed value is
// greater than the current node
else if(value > node.value){
node.right = insert(node.right, value);
}
return node;
}
Searching node in Binary Search tree
Logic for finding a node in binary tree is very similar to binary tree insertion logic. Only difference is that in insertion logic node is inserted when null is encountered where as if null is encountered when searching for a node that means searched node is not found in the binary tree.
Java program to search a node in Binary Search tree
public Node find(int searchedValue){
Node current = root;
while(current.value != searchedValue){
if(searchedValue < current.value)
// Move to the left if searched value is less
current = current.left;
else
// Move to the right if searched value is >=
current = current.right;
if(current == null){
return null;
}
}
return current;
}
Binary tree traversal
When you traverse a tree you visit each node in a specified order. The order that can be used for traversal are-
Binary tree Inorder traversal Java program
Logic for Inorder traversal of binary search tree is as follows-
- Recursively traverse the left subtree
- Visit the root node
- Recursively traverse the right subtree
Note that inorder traversal of the binary search tree visit the nodes in ascending order so inorder traversal is also used for tree sort.
// For traversing in order
public void inOrder(Node node){
if(node != null){
inOrder(node.left);
node.displayData();
inOrder(node.right);
}
}
Binary tree Preoder traversal Java program
Logic for preorder traversal of binary search tree is as follows-
- Visit the root node
- Recursively traverse the left subtree.
- Recursively traverse the right subtree
// Preorder traversal
public void preOrder(Node node){
if(node != null){
node.displayData();
preOrder(node.left);
preOrder(node.right);
}
}
Binary tree Postorder traversal Java program
Logic for postorder traversal of binary search tree is as follows-
- Recursively traverse the left subtree.
- Recursively traverse the right subtree
- Visit the root node
// Postorder traversal
public void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
node.displayData();
}
}
Binary Search tree Java implementation – Insertion, traversal and search node
Here is a complete binary search tree implementation program in Java with methods for inserting a node in BST, traversing binary search tree in preorder, posrtorder and inorder, search a node in binary search tree.
public class BinaryTree {
// first node
private Node root;
BinaryTree(){
root = null;
}
// Class representing tree nodes
static class Node{
int value;
Node left;
Node right;
Node(int value){
this.value = value;
left = null;
right = null;
}
public void displayData(){
System.out.print(value + " ");
}
}
public void insert(int i){
root = insert(root, i);
}
//Inserting node - recursive method
public Node insert(Node node, int value){
if(node == null){
return new Node(value);
}
// Move to the left if passed value is
// less than the current node
if(value < node.value){
node.left = insert(node.left, value);
}
// Move to the right if passed value is
// greater than the current node
else if(value > node.value){
node.right = insert(node.right, value);
}
return node;
}
// Search node in binary search tree
public Node find(int searchedValue){
Node current = root;
while(current.value != searchedValue){
if(searchedValue < current.value)
// Move to the left if searched value is less
current = current.left;
else
// Move to the right if searched value is >=
current = current.right;
if(current == null){
return null;
}
}
return current;
}
// For traversing in order
public void inOrder(Node node){
if(node != null){
inOrder(node.left);
node.displayData();
inOrder(node.right);
}
}
// Preorder traversal
public void preOrder(Node node){
if(node != null){
node.displayData();
preOrder(node.left);
preOrder(node.right);
}
}
// Postorder traversal
public void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
node.displayData();
}
}
public static void main(String[] args) {
BinaryTree bst = new BinaryTree();
bst.insert(50);
bst.insert(70);
bst.insert(15);
bst.insert(35);
bst.insert(30);
bst.insert(31);
System.out.println("Inorder traversal of binary tree");
bst.inOrder(bst.root);
System.out.println();
Node node = bst.find(16);
System.out.println((node == null)? "Node not found" : String.valueOf(node.value));
System.out.println("Preorder traversal of binary tree");
bst.preOrder(bst.root);
System.out.println();
System.out.println("Postorder traversal of binary tree");
bst.postOrder(bst.root);
System.out.println();
}
}
Output
Inorder traversal of binary tree 15 30 31 35 50 70 Node not found Preorder traversal of binary tree 50 15 35 30 31 70 Postorder traversal of binary tree 31 30 35 15 70 50
That's all for this topic Binary Tree Implementation in Java - Insertion, Traversal And Search. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
The insertion on binary tree is not right. The implementation is showed of a binary search tree instead of binary tree. Both of them different. Please have a check on this. The insertion on binary tree is performed using Queue to maintain the balance.
ReplyDeleteIt is clearly mentioned in the post- "Implementation shown here is actually a binary search tree which is a kind of binary tree."
Deleteyour insert method accepts two parameter. 1 Node and 2 value. But in the main you just give 1 parameter...
ReplyDeleteIf you look properly there are 2 overloaded insert method. Following insert method calls the other one. Read more about Method Overloading in Java
Deletepublic void insert(int i){
root = insert(root, i);
}