Hello Trailblazers,

In this tutorial we're going to see how we can insert a new node in binary tree recursively based on the parent node. We're going to refer the code we created in our previous tutorial and add a new **insertData()** method which is going to accept the new data, the parent data and a comparator class. Then it's going to compare if the parent data is equal to the data of any node in the binary tree or not, in case we find such a node, we're going to consider that node as our parent node and we'll link the new node as a child of the parent node. If not, we'll return NULL which means the node cannot be inserted in our binary tree.

### Existing Binary Tree Code

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

**insertData()**method and the new method will insert the data on the basis of parent data. The new

**insertData()**is given below:

/* * Author:- Rahul Malhotra * Description:- This method is used to insert data inside a binary tree based on the parent node's data */ public Node insertData(Object data, Object parentData, Comparator comparator) { // * If root node is NULL, create a new node, assign it as the root node and return that if(root==NULL) { root = new Node(data); return root; } // * Otherwise, call the recursive function using the root node return insertDataRecursive(root, data, parentData, comparator); }

**Comparator**class instance. The comparator class is a custom comparator which will have a method that can be used to compare two objects and will return

**true**if both the objects are equal and will return

**false**if both the objects are not equal.

**insertData()**method is checking if the root node is NULL or not, if it's NULL, we're going to create a new node, assign it as the root node and return that. If the root node exists, we're going to call a private method

**insertDataRecursive()**which is getting the root node, the current object's data and the parent object's data as parameters along with the comparator. Let's have a look at the code of this method to understand how it's working:

/* * Author:- Rahul Malhotra * Description:- This helper method is used to insert data inside a binary tree based on the parent node's data */ private Node insertDataRecursive(Node current, Object data, Object parentData, Comparator comparator) { // * If current node's data is equal to parentData if(comparator.compare(current.data, parentData)) { // * If left child of current node is NULL, add a new node as the left child of the current node and return that if(current.left==NULL) { current.left = new Node(data); return current.left; } // * Else if the right child of current node is NULL, add a new node as the right child of the current node and return that else if(current.right==NULL) { current.right = new Node(data); return current.right; } // * Otherwise, return NULL as the current node already has two nodes and a new node cannot be inserted else { return NULL; } } // * If current node's data is not equal to parentData, check in the left and right subtrees // * If left subtree exists if(current.left!=NULL) { Node left = insertDataRecursive(current.left, data, parentData, comparator); // * If the node is inserted in the left subtree, return the value received from the left subtree if(left!=NULL) { return left; } } // * If right subtree exists if(current.right!=NULL) { Node right = insertDataRecursive(current.right, data, parentData, comparator); // * If the node is inserted in the right subtree, return the value received from the right subtree if(right!=NULL) { return right; } } // * Otherwise, return NULL as the node cannot be inserted return NULL; }

**parentData**using the

**compare()**method of comparator class, if both the data are equal, this means that we can create a new node and add it as a child of the current node. For this, we're checking if the left child of the current node is NULL, we can link the new node as the left child of the current node. Otherwise, if it's right child is NULL, we can link the new node as the right child of the current node. If both the left and right child are not NULL, this means that we don't have any space left to link new node with the current node, so, we return NULL here.

```
/*
* Author:- Rahul Malhotra
* Description:- Binary Tree implementation in apex
* Created Date:- 13-07-2021
* Last Modified:- 14-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;
}
public Object getData() {
return data;
}
}
// * 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 insert data inside a binary tree based on the parent node's data
*/
public Node insertData(Object data, Object parentData, Comparator comparator) {
// * If root node is NULL, create a new node, assign it as the root node and return that
if(root==NULL) {
root = new Node(data);
return root;
}
// * Otherwise, call the recursive function using the root node
return insertDataRecursive(root, data, parentData, comparator);
}
/*
* Author:- Rahul Malhotra
* Description:- This helper method is used to insert data inside a binary tree based on the parent node's data
*/
private Node insertDataRecursive(Node current, Object data, Object parentData, Comparator comparator) {
// * If current node's data is equal to parentData
if(comparator.compare(current.data, parentData)) {
// * If left child of current node is NULL, add a new node as the left child of the current node and return that
if(current.left==NULL) {
current.left = new Node(data);
return current.left;
}
// * Else if the right child of current node is NULL, add a new node as the right child of the current node and return that
else if(current.right==NULL) {
current.right = new Node(data);
return current.right;
}
// * Otherwise, return NULL as the current node already has two nodes and a new node cannot be inserted
else {
return NULL;
}
}
// * If current node's data is not equal to parentData, check in the left and right subtrees
// * If left subtree exists
if(current.left!=NULL) {
Node left = insertDataRecursive(current.left, data, parentData, comparator);
// * If the node is inserted in the left subtree, return the value received from the left subtree
if(left!=NULL) {
return left;
}
}
// * If right subtree exists
if(current.right!=NULL) {
Node right = insertDataRecursive(current.right, data, parentData, comparator);
// * If the node is inserted in the right subtree, return the value received from the right subtree
if(right!=NULL) {
return right;
}
}
// * Otherwise, return NULL as the node cannot be inserted
return NULL;
}
/*
* 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');
}
}
}
```

**insertData()**and

**insertDataRecursive()**methods are complete. Let's have a look at the comparator class as well:

```
/*
* Author:- Rahul Malhotra
* Description:- Comparator class to be used in Binary Tree
* Created Date:- 14-07-2021
* Last Modified:- 14-07-2021
* Code Origin:- SFDC Stop (https://www.sfdcstop.com)
*/
public abstract class Comparator {
public abstract Boolean compare(Object o1, Object o2);
}
```

**Comparator**is an abstract class which is having a single abstract method definition, this method is going to receive two objects and return a Boolean

**true**if both the objects are equal and

**false**if both the objects are not equal. We have created this abstract class to keep our binary tree code independent of data types as we can implement a child of this abstract class and do the comparison there. For example: Let's consider that in our case, we need to compare integers, so, we can create another class as shown below:

/* * Author:- Rahul Malhotra * Description:- This helper class is used to compare two integers. * It's used in the creation of binary tree */ public class IntegerCompare extends Comparator { public override Boolean compare(Object o1, Object o2) { return (Integer) o1 == (Integer) o2; } }

IntegerCompare integerCompare = new IntegerCompare(); BinaryTree tree = new BinaryTree(); tree.insertData(1, null, integerCompare); tree.insertData(2, 1, integerCompare); tree.insertData(3, 1, integerCompare); tree.insertData(7, 3, integerCompare); tree.insertData(4, 2, integerCompare); tree.levelOrderPrint();

**O(n^2)**. How? Let's consider the tree given below:

**O(n)**. Therefore, for insertion of n nodes, the total time taken will be

**O(n*n) = O(n^2)**. Such type of tree is also known as a

**Skew Tree**. We can improve this time complexity by doing a slight modification in the code. Now, that's a homework for you. Think about how you can insert a node in this tree faster and let me know your solution in the comments down below.

**apex-data-structures**Github Repository here.

**Happy Trailblazing..!!**

## No comments:

## Post a Comment