Insertion in Binary Tree based on parent node | Custom comparator in Apex | Apex Data Structures Tutorial by SFDC Stop

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.

Tutorial Video

Existing Binary Tree Code

Let's have a quick look at the present code of binary tree from the previous tutorial, before we begin:

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

In the above class, we're going to overload the 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);
}

As you can see above, this method is receiving the current data which we need to add to the binary tree, the parent data which is the data of parent node present in the binary tree and a 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.

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

This method will start from the root node and will traverse the whole tree recursively in order to find a node whose data is equal to our parentData. If such a node is found, a new node will be created with the given data and will be inserted as a child of this node, otherwise, NULL will be returned.

As you can see, first of all we're comparing the current node's data with the 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.

If the current node's data is not equal to the parentData, we'll try to insert the node somewhere in the left subtree. If the node is inserted in the left subtree i.e. we get a non NULL value from there, we can simply reutrn that. Otherwise, we can repeat the same process for the right subtree. If we're getting NULL from both the subtrees or if none of left or right subtree exist, this means that, we cannot insert the new node anywhere, therefore we return NULL.

The updated code for the BinaryTree class with both these methods included is given below:

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

Now, our 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);
}

As you can see above, 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;
    }
}

This IntegerCompare class is extending our abstract Comparator class and is implementing the compare method. For our binary tree, we're checking if both the objects (when typecasted to Integers) are equal or not. If both the Integers are equal, the method will return true, otherwise, it'll return false.

It's time to test our new insertData() method now. Let's consider the below binary tree.

As you can see above, this is not a complete binary tree as the node 1 has two nodes 2 and 3. But both the nodes 2 and 3 have 1 node each as their child. We can use the below code snippet to create this binary tree and print the nodes level by level using the levelOrderPrint():

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();

Let's have a look at the output as well:

As you can see above, we're getting the node 1 at level 1, node 2, 3 at level 2 and node 4, 7 at level 3. Therefore, we can say that the code is working perfectly fine and we're able to insert the nodes by finding the parent node.

The actual tree that is created will be a little different from the tree image that we've seen above. It'll look as shown below:

Note that the child node of 3 i.e. node 7 will be on the left side and not on the right side. This is because we're not passing any directions with each node to identify if it should be linked as left or right child and by default as per our code, we're inserting the node as the left child, if the left child of parent node is NULL.

The worst case time complexity of this insertion algorithm will be O(n^2). How? Let's consider the tree given below:

In this case, for insertion of each node we have to traverse through n nodes that are present in the tree. Therefore time taken to insert each node in the tree is 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.

The whole code for this tutorial can be accessed in the apex-data-structures Github Repository here.

That's all for this tutorial everyone, I hope you liked it and understood the concept of custom comparator, it's usage and how we can insert a new node in an incomplete or complete binary tree by checking value of the parent node.

Happy Trailblazing..!!