Hello 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; } }

### Insertion in Binary Tree

**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; } } }

**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.

### Level Order Print of Binary Tree

/* * 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'); } }

**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.

**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.

### Creating Binary Tree from a list of elements

/* * 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); } }

### Code Execution and Output

BinaryTree tree = new BinaryTree(); tree.createBinaryTree(new List<Integer>{1,2,3,4,5,6,7}); tree.levelOrderPrint();

**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.

**Object**everywhere as the data type instead of a specific data type such as

**String**or

**Integer**. Object is a generic data type in salesforce which can be used as a template to handle other data types. This is the reason it's working fine when we passed a list of integers to create a tree. Let's pass a list of strings this time to see if that works:

BinaryTree tree = new BinaryTree(); tree.createBinaryTree(new List<String>{'A','B','C','D','E','F','G'}); tree.levelOrderPrint();

**generic**and can be used with different data types.

**apex-data-structures**github repository here.

**Happy Trailblazing..!!**

## No comments:

## Post a Comment