Table of Contents
A binary tree, also known as a binomial tree, is the most basic representation of any tree data structure in computer science. In this post, we’ll cover how to implement binary trees in Java that may be different from what you learned in your class or on Codecademy, but which will cover all of the same core topics and more! A binary tree is a type of data structure used to store data, with each node holding some values that may have children. A typical tree structure can be viewed as an inverted tree in which the topmost node, also known as the root, points to its child nodes (if any) or its parent node (if it has no children). This data structure can be found throughout nature and in various programming languages, including Java. Here are the ways to implement a binary tree in Java using the popular Java collections library.
What is a binary tree?
A binary tree is an organized collection of nodes, with one node designated as the root of the tree and all other nodes being children of the root node, much like an upside-down tree. A binary tree can be either sorted or unsorted, depending on whether its nodes are arranged from left to right in order of value (an ordered binary tree) or in no particular order (an unordered binary tree). Creating your own data structure to represent a binary tree in Java can help you solve problems such as keeping track of data within an organization, giving you the ability to maintain relationships between two sets of information efficiently and effectively.
Get the latest updates on java programming in the Entri app
Types of Binary Trees
1: What is the default value of a boolean in Java?
Full Binary Tree
A full binary tree is a binary tree where every node has either no children or two children.
Perfect Binary Tree
A binary tree is considered to be a perfect binary Tree if every node has two children, and all leaf nodes are at the same level.
Complete Binary Tree
A complete binary tree is a binary tree where each of its levels, excluding the last one, are entirely filled with nodes, and all of its nodes are as far to the left side as possible.
Implementation of Binary Tree
For the implementation, there’s an auxiliary Node class that stores integers and has references to all of its children. The first step is finding the spot where we want to insert a new node in order to maintain the tree’s structural integrity. We’ll follow these guidelines starting at the root node
- if new node’s value is lower than the current node’s, go to the left child
- if new node’s value is greater than the current node’s, go to the right child
- when current node is null, we’ve reached a leaf node, we insert the new node in that position
Example
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
|
package MyPackage; public class Tree { static class Node { int value; Node left, right; Node(int value){ this.value = value; left = null; right = null; } } public void insert(Node node, int value) { if (value < node.value) { if (node.left != null) { insert(node.left, value); } else { System.out.println(" Inserted " + value + " to left of " + node.value); node.left = new Node(value); } } else if (value > node.value) { if (node.right != null) { insert(node.right, value); } else { System.out.println(" Inserted " + value + " to right of " + node.value); node.right = new Node(value); } } } public void traverseInOrder(Node node) { if (node != null) { traverseInOrder(node.left); System.out.print(" " + node.value); traverseInOrder(node.right); } } public static void main(String args[]) { Tree tree = new Tree(); Node root = new Node(5); System.out.println("Binary Tree Example"); System.out.println("Building tree with root value " + root.value); tree.insert(root, 2); tree.insert(root, 4); tree.insert(root, 8); tree.insert(root, 6); tree.insert(root, 7); tree.insert(root, 3); tree.insert(root, 9); System.out.println("Traversing tree in order"); tree.traverseLevelOrder(); }} |
Output:
|
1
2
3
4
5
6
7
8
9
10
11
|
Binary Tree ExampleBuilding tree with root value 5 Inserted 2 to left of 5 Inserted 4 to right of 2 Inserted 8 to right of 5 Inserted 6 to left of 8 Inserted 7 to right of 6 Inserted 3 to left of 4 Inserted 9 to right of 8Traversing tree in order 2 3 4 5 6 7 8 9 |
Get the latest updates on java programming in the Entri app
Tree Traversals
Trees can be traversed in many different ways: Let’s use the same tree example that we used before for each case.
Depth First Search
Depth-first search is a type of traversal where you go as deep as possible down one path before backing up and trying a different one. In order, pre-order or post-order – there are many methods to try when it comes to this kind of algorithm.
Pre-Order Traversal
In pre-order traversal, you always start from the root node first before going to either of its two children. This is an example of how this works in Python code
|
1
2
3
4
5
6
7
|
public void traversePreOrder(Node node) { if (node != null) { System.out.print(" " + node.value); traversePreOrder(node.left); traversePreOrder(node.right); }} |
Output:
|
1
|
5 2 4 3 8 6 7 9 |
Get the latest updates on java programming in the Entri app
Post-Order Traversal
In Post-order traversal you visit the left subtree first, then the right subtree, and the root node at the end. Here’s the code.
|
1
2
3
4
5
6
7
|
public void traversePostOrder(Node node) { if (node != null) { traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.value); }} |
Output:
|
1
|
3 4 2 7 6 9 8 5 |
Breadth-First Search
This type of traversal is much like throwing a stone in the center of a pond and observing how it ripples out from there. This function goes to each node at every level before moving on to the next, just as if one were reading an encyclopedia article where they travel through information starting at A and working their way down to Z. Level order or breadth-first search are both names for this technique because it starts at the root or top of a tree and moves its way down.
Applications of Binary Tree
Applications of binary trees include:
- Used in many search applications where data is constantly entering or leaving.
- As a workflow for compositing digital images for visual effects.
- Used in almost every high-bandwidth router for storing routing tables.
- Also used in wireless networking and memory allocation.
- Used in compression algorithms and other programs.
Using ArrayList
ArrayList provides an efficient way of storing data and is easy to implement using an array. But, as everything has its disadvantages, so does ArrayList. One disadvantage of ArrayList is that it doesn’t provide any sorting or search capability out-of-the-box. We can sort elements of an ArrayList if we copy them into another List object and then sort that list; but that may not be efficient for large lists. Searching for specific data from within a huge list is also inefficient since we need to compare each element with our data point until we locate it or conclude that our data wasn’t found. The performance of both these operations depends on how many items are stored in your ArrayList. A more efficient approach would be to use other collection classes provided by Java such as LinkedHashSet and LinkedHashMap, which allow you to store your data while maintaining its order (LinkedHashSet) or while searching for data efficiently (LinkedHashMap). In fact there are some issues of implementing binary tree using arrays. You will lose time when adding and removing data because of having to resize arrays all over again every time you add or remove one node. Also making changes like deleting, reordering etc. will cost time because they have to recalculate nodes indexes based on changed parent index value. If you know what data type you want to hold inside nodes, it might be better idea to make array of appropriate size right at start. And holding reference of head node in class variable makes insertion/deletion faster and easier because no need to calculate position of head node anymore. Use LinkedHashMap instead: Another option is use java Map interface instead of ArrayList.
Node Interface
The goal of creating a node interface is to make it easier for us to create nodes and ensure that our nodes will be compatible with each other. The only important thing we need to know about every node in our tree is what its data is, so let’s start there. We will define each node as an object that contains one other object—its value. A Node interface might look like Listing 1.1 . Note that since we want to be able to store any type of object in a node, we are using generics. Generics allow us to tell Java exactly what type of objects can go into a particular variable or class. Since we are going to be implementing binary trees (each node has at most two children), we have defined Node as having only one child. Of course, you could always change your mind later on if you wanted to add more functionality. This interface also defines two methods: getValue() and setValue() . These methods return and set a node’s value respectively. By defining these methods here, they will automatically become available on all subclasses of Node , which is convenient because subclasses must implement these methods themselves anyway. For example, when designing a new subclass of BinaryTreeNode , if you did not define these methods yourself, then calling myBinaryTreeNode2.getValue() would cause compilation errors because no such method exists! However, if you did define them, then calling myBinaryTreeNode2.getValue() would just work fine; your implementation of getValue() would simply execute instead. As another example, suppose you were working on a completely different project and needed to create a custom sorting algorithm; defining Comparable methods in some sort of common superclass may be very useful. The second part of our Node interface is a constructor that takes two parameters: data and leftChild . The constructor allows us to easily instantiate nodes by supplying their values and left children right away rather than requiring us to write code elsewhere that creates nodes manually from scratch.
Get the latest updates on java programming in the Entri app
Conclusion
I’ve tried to cover everything you need to know about implementing binary trees in Java. Now it’s up to you to build your own implementation of them, and use them as they should be used—to store data! I wish you luck, because binary trees are truly one of those things that don’t get enough love. There are so many great uses for them that make using them worth every bit of effort. And there’s also always room for improvement on your part. Maybe someday we can see your awesome code on GitHub or elsewhere! Until then…see ya! 🙂 As you can see, articles like these will teach readers how to start blogging, which is essential for anyone who wants to build their personal brand and start earning income online. If you are interested to learn new coding skills, the Entri app will help you to acquire them very easily. Entri app is following a structural study plan so that the students can learn very easily. If you don’t have a coding background, it won’t be any problem. You can download the Entri app from the google play store and enroll in your favorite course.
