'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Jun 30, 2023
Medium

Implementing a Binary Tree in Java

Author Lucifer go
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

A tree is a famous non-linear data structure. Unlike other data structures like an array, queue, stack, and linked list, which are linear, a tree represents a hierarchical structure for storing data. A tree consists of nodes that have 2 pointers. These two pointers point to the parent node's left child and the right child. 

A tree whose nodes have at most 2 children is called a binary tree. In this blog, we'll cover the implementation of a binary tree in Java. We'll use a sorted binary tree that consists of int values for its implementation.

Tree Terms

Here we will be discussing some important terms with respect to binary trees: -

  • Root: The root of a tree is the tree's topmost node with no parent node. Only one root node can exist in a binary tree.
  • Edge: Edge acts as a connector between the parent node and the child node.
  • Leaf: A leaf nodes have no child nodes. A leaf node can be more than one.
  • Depth: The depth is the distance of a node from the root node.
  • Height: The node's height is the distance from that node to the deepest node of the tree.
  • Height of tree: It is the maximum height from the height of every node.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Why use Tree?

  • One reason to use trees is to store data that form a hierarchy. A file system on a computer may follow this sort of hierarchy: 
  • Trees like BST provide moderate access and search (faster than Linked List and slower than arrays). 
  • Trees provide moderate insertion and deletion (faster than Arrays and slower than Unordered Linked Lists). 
  • Unlike Arrays, Trees don’t have an upper limit on the number of nodes as nodes are linked using pointers.

Implementation of Binary Tree Operations

Inserting Elements

  • First, locate the place where we need to insert the node.
  • Traverse to the left child if the new node's value is lower than the current node's value.
  • Traverse to the right child if the new node's value is greater than the current node's value.
  • If the current node is null, we've reached a leaf node and hence we can insert the new node in that position. Then we can follow a recursive method for insertion.
     
private Node Recursive_Addition(Node curr_node, int val) {
    if (curr_node == null) {
        return new Node(val);
    }
   else if (val < curr_node.val) {
        curr_node.left = Recursive_Addition(curr_node.left, val);
    } else if (val > curr_node.val) {
        curr_node.right = Recursive_Addition(curr_node.right, val);
    } else {
        // val already exists
        return curr_node;
    }
   return curr_node;
}
public void add(int val) {
    root = Recursive_Addition(root, val);
}

Finding an Element

  • Create a recursive method that traverses the tree.
  • Search for the value by comparing it to the value of the current node and then continue left or right depending upon the outcome.
     
private boolean find_node(Node current_node, int val) {
    if (current_node == null) {
        return false;
    } 
    if (val == current_node.val) {
        return true;
    } 
    return val < current_node.val
      ? find_node(current_node.left, val)
      : find_node(current_node.right, val);
}
public boolean containsNode(int val) {
    return find_node(root, val);
}

Deleting an Element

First, find the node to be deleted similarly as before. Once the node is found, there are 3 prominent different cases:

  • A node has no children: Need to replace this node with null in its parent node.
  • A node has one child: In the parent node, we replace this node with its only child.
  • A node has two children: Requires a tree reorganization.
     
private Node delete_recursive(Node current_node, int val) {
    if (current_node == null) {
        return null;
    }
    if (val == current_node.val) {
        // ... deletion code
    } 
    if (val < current_node.val) {
        current_node.left = delete_recursive(current_node.left, val);
        return current_node;
    }
    current_node.right = delete_recursive(current_node.right, val);
    return current_node;
}
   if (current_node.left == null && current_node.right == null) {
    return null;
}
// If node has one child:
if (current_node.right == null) {
    return current_node.left;
}
if (current_node.left == null) {
    return current_node.right;
}
private int smallest_value(Node root) {
    return root.left == null ? root.val : smallest_value(root.left);
}
int smallestValue = smallest_value(current_node.right);
current_node.val = smallestValue;
current_node.right = delete_recursive(current_node.right, smallestValue);
return current_node;
public void delete(int val) {
    root = delete_recursive(root, val);
}

Depth-First Search

It is a type of traversal that goes deep into a node as possible in every child and then explores the next sibling of the currently visited node.

Ways to perform a depth-first search: -

Inorder - the left subtree, then the root node, and finally the right sub-tree.

public void InOrder(Node node) {
    if (node != null) {
        InOrder(node.left);
        System.out.print(" " + node.value);
        InOrder(node.right);
    }
}


Pre-Order - the root node, then the left sub-tree, and finally the right sub-tree.

public void PreOrder(Node node) {
    if (node != null) {
        System.out.print(" " + node.value);
        PreOrder(node.left);
        PreOrder(node.right);
    }
}


Post-Order - the left subtree, then the right sub-tree, and finally the root node

public void PostOrder(Node node) {
    if (node != null) {
        PostOrder(node.left);
        PostOrder(node.right);
        System.out.print(" " + node.value);
    }
}

Breadth-First Search

In this traversal, the pointer visits all the nodes of a level before going to the next level. We use the queue data structure for implementation.

public void traverseLevelOrder() {
    if (root == null)
        return;
 Queue<Node> nodes = new List<>();
    nodes.add_node(root);
    while (!nodes.isEmpty()) {
        Node node = nodes.remove();
        System.out.print(" " + node.value);
        if (node.left != null) 
            nodes.add_node(node.left);
        if (node.right != null) 
            nodes.add_node(node.right);
    }
}

Frequently Asked Questions

What is a full binary tree?

A full binary tree is a binary tree where every node has exactly either 0 or 2 children.

What is a perfect binary tree?

If every internal node has two offspring and every leaf is at the same level, then it is a perfect binary tree.

What is a complete binary tree?

Every level of a binary tree, maybe with the exception of the final, must be fully filled, and all the other nodes must be as far to the left as feasible.

What are the applications of binary trees?

Applications of binary trees include:

  • Used in almost every high-bandwidth router for storing router tables.
  • Used in search applications where data is constantly entering or leaving.
  • Used in wireless networking and memory allocation.
  • Used in algorithms for compression and many more.

What are the different types of tree traversals?

Different types of tree traversals include pre-order traversal, post-order traversal, inorder traversal, and level order traversal.

Conclusion

In this article, we have extensively discussed implementing a Binary Tree in Java and performing various operations on it.

 

Recommended problems -

 

You can also check our previous blogs on JAR filesAzure Cognitive Search, and View and View Controllers. If you are eager to learn advanced front-end web development, Coding Ninjas is here with one of the best courses available, which you can find here.

Happy Learning!

Previous article
BFS vs DFS for Binary Tree
Next article
N-Ary Trees
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass