Thursday, March 7, 2019

Binary Tree Implementation in Java - Insertion, Traversal And Search

In this post we’ll see an implementation of binary tree in Java. Operations covered in this post are-

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

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

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

  1. Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program
  2. Doubly Linked List Implementation Java Program
  3. Interpolation Search Program in Java
  4. Shell Sort Program in Java
  5. Armstrong Number or Not Java Program

You may also like-

  1. Creating PDF in Java Using iText
  2. How to Create Password Protected Zip File in Java
  3. Converting String to Byte Array - Java Program
  4. Array Rotation Java Program
  5. Just In Time Compiler (JIT) in Java
  6. Method Reference in Java
  7. static Block in Java
  8. Spring Bean Life Cycle