Join our Telegram ChannelHello Trailblazers,
In this post we're going to talk about how we can create a Binary Tree in Apex. Let's see how a Binary Tree looks like:
As you can see above, we have a root node which is 1 in the above image, and each node in the tree can have two children at max. In the above tree, the nodes: 4 5 6 and 7 are called leaf nodes as they have no children.
Tutorial Video
Let's have a quick look at the full code once, then we'll discuss everything in detail.
/* * Author:- Rahul Malhotra * Description:- Binary Tree implementation in apex * Created Date:- 13-07-2021 * Last Modified:- 13-07-2021 * Code Origin:- SFDC Stop (https://www.sfdcstop.com) */ public class BinaryTree { // * Node class public class Node { Object data; Node left; Node right; public Node(Object data) { this.data = data; this.left = NULL; this.right = NULL; } } // * Root of binary tree Node root; // * Method to insert data in binary tree private void insertData(Object data) { // * If root is NULL, create a new node and return if(root==NULL) { root = new Node(data); return; } // * Initializing a queue of nodes List<Node> nodesQueue = new List<Node>(); // * Adding root node to the queue nodesQueue.add(root); // * Looping while queue is not empty while(!nodesQueue.isEmpty()) { // * Getting the current node and removing it from the queue Node current = nodesQueue.get(0); nodesQueue.remove(0); // * If the left child of current node is not null, add it to the queue if(current.left!=NULL) { nodesQueue.add(current.left); } // * Otherwise, create a new node and attach it as the left child else { current.left = new Node(data); return; } // * If the right child of current node is not null, add it to the queue if(current.right!=NULL) { nodesQueue.add(current.right); } // * Otherwise, create a new node and attach it to the right child else { current.right = new Node(data); return; } } } /* * Author:- Rahul Malhotra * Description:- This method is used to create a binary tree */ public void createBinaryTree(List<Object> elements) { // * Inserting elements in binary tree for(Object element : elements) { insertData(element); } } /* * Author:- Rahul Malhotra * Description:- This method is used to print binary tree level by level */ public void levelOrderPrint() { // * Checking if root is not NULL if(root!=NULL) { String result = '\n'; // * Initializing a queue List<Node> nodesQueue = new List<Node>(); // * Adding root node to the queue nodesQueue.add(root); // * Looping while queue is not empty while(!nodesQueue.isEmpty()) { // * Getting nodes at current level Integer nodesAtCurrentLevel = nodesQueue.size(); // * Looping while nodes at current level is more than 0 while(nodesAtCurrentLevel>0) { // * Getting the current node and removing it from the queue Node current = nodesQueue.get(0); nodesQueue.remove(0); // * Adding current node data to the result result += current.data + ' '; // * If left child of the current node is not NULL, add it to the queue if(current.left!=NULL) { nodesQueue.add(current.left); } // * If right child of the current node is not NULL, add it to the queue if(current.right!=NULL) { nodesQueue.add(current.right); } // * Decrementing nodes at current level by 1 nodesAtCurrentLevel--; } // * Adding a new line to the result for next level result += '\n'; } // * Displaying the result System.debug(result); } // * If root is NULL, display error message else { System.debug('Tree not found'); } } }
Creating Node class
// * Node class
public class Node {
Object data;
Node left;
Node right;
public Node(Object data) {
this.data = data;
this.left = NULL;
this.right = NULL;
}
}
As you can see above, we've created a simple node class. Each node of the binary tree will consist of data and references to the left and right child of the current node.
Insertion in Binary Tree
The insertData method is used to insert a new node in binary tree:
// * Root of binary tree Node root; // * Method to insert data in binary tree private void insertData(Object data) { // * If root is NULL, create a new node and return if(root==NULL) { root = new Node(data); return; } // * Initializing a queue of nodes List<Node> nodesQueue = new List<Node>(); // * Adding root node to the queue nodesQueue.add(root); // * Looping while queue is not empty while(!nodesQueue.isEmpty()) { // * Getting the current node and removing it from the queue Node current = nodesQueue.get(0); nodesQueue.remove(0); // * If the left child of current node is not null, add it to the queue if(current.left!=NULL) { nodesQueue.add(current.left); } // * Otherwise, create a new node and attach it as the left child else { current.left = new Node(data); return; } // * If the right child of current node is not null, add it to the queue if(current.right!=NULL) { nodesQueue.add(current.right); } // * Otherwise, create a new node and attach it to the right child else { current.right = new Node(data); return; } } }
We have created a data member of the main class named as root which will store the root of a binary tree. Inside insertData method, we're receiving the data as a parameter. After that we're checking, if root is NULL, we create a new node, assign it as the root of the tree and return.
In case we have a root of the tree defined, we initialize a queue of nodes and add the root node to the queue. This queue is mainly used to traverse the tree level by level so that we can add the new node to the tree at the next available position.
We're looping while the queue is not empty, in each iteration, we get the current node from the queue. After that we check if the left child of the current node is NULL or not. If it's NULL that means we can add our new node at this position and return, if not, we're going to add the left child to the queue and we're going to repeat the same process for the right child.
Level Order Print of Binary Tree
The below method is used to print all nodes of the binary tree level by level:
/* * Author:- Rahul Malhotra * Description:- This method is used to print binary tree level by level */ public void levelOrderPrint() { // * Checking if root is not NULL if(root!=NULL) { String result = '\n'; // * Initializing a queue List<Node> nodesQueue = new List<Node>(); // * Adding root node to the queue nodesQueue.add(root); // * Looping while queue is not empty while(!nodesQueue.isEmpty()) { // * Getting nodes at current level Integer nodesAtCurrentLevel = nodesQueue.size(); // * Looping while nodes at current level is more than 0 while(nodesAtCurrentLevel>0) { // * Getting the current node and removing it from the queue Node current = nodesQueue.get(0); nodesQueue.remove(0); // * Adding current node data to the result result += current.data + ' '; // * If left child of the current node is not NULL, add it to the queue if(current.left!=NULL) { nodesQueue.add(current.left); } // * If right child of the current node is not NULL, add it to the queue if(current.right!=NULL) { nodesQueue.add(current.right); } // * Decrementing nodes at current level by 1 nodesAtCurrentLevel--; } // * Adding a new line to the result for next level result += '\n'; } // * Displaying the result System.debug(result); } // * If root is NULL, display error message else { System.debug('Tree not found'); } }
In this method as well, we're using the same logic as specified in the insertion method. First of all, we're checking:- If the root node is not NULL, we'll proceed forward, if it's NULL, we're going to simply display the message as: Tree not Found which means we haven't added any element to the binary tree yet. After that we're creating a queue of nodes, inserting the root node in that queue and looping the queue while it's not empty.
In each iteration, we're getting the total number of nodes present in the queue which is nothing but the total number of nodes present at the current level in the binary tree. We're storing that count in nodesAtCurrentLevel variable. Then, we're having another loop which will process all the nodes at the current level together. For each iteration of this inner loop, we're getting the node at the front of the queue and removing it from the queue. Then, we're adding the data of current node to our result string. After that we're checking if the left and right child of the current node is not NULL, if so, we're going to add those to the queue as well. Finally, we're decrementing the nodesAtCurrentLevel variable by 1 as we have processed one node present at the current level.
If you see carefully, the only difference here and in insertion method is that, here we're getting the number of nodes present in the current level, processing all those nodes together and adding a new line in the result string after processing so that we can display all the nodes at the current level in the same line. This is added only for formatting purposes.
At the end, we're displaying the result string.
Creating Binary Tree from a list of elements
Now it's time to create our binary tree using the insertData method. Let's have a look at the below method which will accept the list of elements from the user and will create a binary tree by passing each element one by one into the insertData method.
/*
* Author:- Rahul Malhotra
* Description:- This method is used to create a binary tree
*/
public void createBinaryTree(List<object> elements) {
// * Inserting elements in binary tree
for(Object element : elements) {
insertData(element);
}
}
This is a fairly simple method where we're iterating all the elements using a for loop and adding them to our binary tree one by one.
Code Execution and Output
Congratulations! You've created a binary tree in apex by yourself. Now, it's time to execute the code and verify the result. Let's have a look at the below code snippet:
BinaryTree tree = new BinaryTree();
tree.createBinaryTree(new List<Integer>{1,2,3,4,5,6,7});
tree.levelOrderPrint();
As you can see above, we're simply creating an object of our BinaryTree class, then we're creating a binary tree by passing a list of integers and we're finally printing the binary tree elements level by level. After executing the above code, you'll get the output as shown below:
As you can see above, the first element of our list is the root node i.e. 1, after that the two elements 2 and 3 are inserted in the tree at the second level as the child of 1. And the other remaining elements, 4 5 6 and 7 are inserted at the third level in the binary tree. These nodes at the last level of the binary tree are called leaf nodes. Therefore, in our above example, 4 5 6 and 7 are leaf nodes.
BinaryTree tree = new BinaryTree();
tree.createBinaryTree(new List<String>{'A','B','C','D','E','F','G'});
tree.levelOrderPrint();
As you can see above, this time we are passing a list of strings instead of integers, let's see the output when the above code is executed:
As you can see above, this time also, we're getting the correct output as the tree is created successfully. This means that our code is generic and can be used with different data types.
So, that's all for this tutorial everyone, I hope you learned something new. Try to implement this by your own and let me know if you have any questions in the comments down below. You can find the full code for this tutorial in the apex-data-structures github repository here.
Happy Trailblazing..!!
Posts
No comments:
Post a Comment