The importance of Data Structures in Salesforce Development | Live Session at Cactusforce 2022

Hello Trailblazers,

This post consist of the presentation, problem statement and the solution code that was used in the live session on "The importance of Data Structures in Salesforce Development" at Cactusforce 2022. The full session abstract can be viewed here.

In this session, we solved a real life project requirement using an advanced data structure and we also had a look at the performance impact we had by using it and learned why it is better than a brute force solution. So, the next time when you face such a requirement, you'll think at the first place - Which data structure should I use to solve it? and then you'll design and implement the most efficient solution.

Session Video

The importance of Data Structures in Salesforce Development - Rahul Malhotra from Marisa Hambleton on Vimeo.

Slides

The importance of Data Structures in Salesforce Development | Live Session at Cactusforce 2022 from Rahul Malhotra

Problem Statement

We have a custom field on account named as: UltimateParentAccount__c, this field is a lookup to account and will specify the ultimate parent of any account in the hierarchy. For example, in the below accounts hierarchy:

In every node: 

• The letter in black is the current account's name. 
• The letter in red represents the parent account (value in ParentId) of the current account
• The letter in blue represents the ultimate parent account for the current account i.e. the value in UltimateParentAccount__c field.

We have to implement a solution for the event when the current account is updated, to make sure that the UltimateParentAccount__c field for the current account, as well as for the accounts in the hierarchy below have the correct value. We need to take into account, below scenarios for this:

1. Current account parent is null and is updated to a new value
2. Current account parent is populated and is updated to null
3. Current account parent is populated and is updated to a new value

In all these cases, the UltimateParentAccount__c field should be update to a new value on the current account as well as, on the accounts below the current account.

Solution code snippet

Please find all the solution code snippets related to this problem statement below. We've implemented the solution to this problem using N-Ary Trees:

N-Ary Tree

/*
*	Author:- Rahul Malhotra
*	Description:- NAry Tree implementation in apex
*	Created Date:- 14-01-2022
*	Last Modified:- 19-01-2022
*       Code Origin:- SFDC Stop (https://www.sfdcstop.com)
*/
public class NAryTree {

    // * Node class
    public class Node {

        // * Data members
        sObject data;
        Map<Id, Node> childNodesMap;

        // * Member functions
        public Node(sObject data) {
            this.data = data;
        }

        public sObject getData() {
            return data;
        }

        public Map<Id, Node> getChildNodesMap() {
            return childNodesMap;
        }
    }

    // * Data members
    Node root;

    /*
    *   Description: This method is used to return root of the tree
    */
    public Node getRoot() {
        return root;
    }

    /*
    *   Description: This method is used to insert a new node in a tree
    */
    public Boolean insertData(sObject currentRecord, sObject parentRecord, Comparator comparator) {

        /*
        *   If root node is NULL, creating a new root node
        *   and adding assigning it as the root node
        */
        if(root==NULL) {
            root = new Node(currentRecord);
            return true;
        }

        // * Otherwise, adding the current record to the subtree under the correct parent node
        return insertDataRecursive(root, currentRecord, parentRecord, comparator);
    }

    /*
    *   Description: This method is used to insert the new node in the tree
    *   by recursively traversing the tree to find the correct position
    */
    private Boolean insertDataRecursive(
        Node current,
        sObject currentRecord,
        sObject parentRecord,
        Comparator comparator
    ) {

        /*
        *   If current node's data is equal to parentRecord,
        *   adding new node to the current node's child
        */
        if(comparator.compare(current.data, parentRecord)) {
            if(current.childNodesMap == null) {
                current.childNodesMap = new Map<Id, Node>();
            }
            Node newNode = new Node(currentRecord);
            current.childNodesMap.put((Id) currentRecord.get('Id'), newNode);
            return true;
        }

        // * If current node's data is not equal to parentRecord, check in the current node's child subtrees
        if(current.childNodesMap!=null) {
            List<Node> childNodes = current.childNodesMap.values();
            for(Node childNode : childNodes) {
                if(insertDataRecursive(childNode, currentRecord, parentRecord, comparator)) {
                    return true;
                }
            }
        }

        // * Otherwise, return false as the node cannot be inserted
        return false;
    }

    /*
    *   Description: This method is used to delete a tree based on the root node
    *   provided in the parameter
    */
    public void deleteTree(Node root) {

        // * If root node is not NULL, proceed ahead
        if(root!=NULL) {

            // * Get the child nodes for the current node
            Map<Id, Node> childNodesMap = root.getChildNodesMap();
            // * If there are child nodes present
            if(childNodesMap!=NULL) {
                /*
                *   Recursively call the deleteTree() method to delete current child
                *   node as well as subtrees under these child nodes
                */
                for(Node currentNode : childNodesMap.values()) {
                    deleteTree(currentNode);
                }
            }

            // * Remove the root node from the tree
            root = NULL;
        }
    }

    /*
    *   Description: This method is used to perform a level order traversal
    *   of the whole tree and display the nodes information
    */
    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.get('Id') + ' ' + current.data.get('Name') + ' -> ' + current.data.get('ParentId') + ' ';
                    // * Adding the child nodes for the current node to the queue
                    if(current.childNodesMap!=NULL) {
                        List<Node> childNodes = current.childNodesMap.values();
                        for(Node childNode : childNodes) {
                            nodesQueue.add(childNode);
                        }
                    }
                    // * 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');
        }
    }
}

IdCompare Class

/*
*       Author:- Rahul Malhotra
*       Description:- This helper class is used to compare two records based on their ids.
*	Created Date:- 14-01-2022
*	Last Modified:- 19-01-2022
*       Code Origin:- SFDC Stop (https://www.sfdcstop.com)
*/
public class IdCompare extends Comparator {
    public override Boolean compare(sObject o1, sObject o2) {
        return (Id) o1.get('Id') == (Id) o2.get('Id');
    }
}

Comparator Class

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

Accounts Trigger

/*
*       Author:- Rahul Malhotra
*       Description: This is the trigger on account object
*	Created Date:- 14-01-2022
*	Last Modified:- 19-01-2022
*       Code Origin:- SFDC Stop (https://www.sfdcstop.com)
*/
trigger AccountsTrigger on Account (after update) {

    // * Marking accounts whose parent is updated
    List<Account> accountsWithUltimateParentUpdate = new List<Account>();
    if(trigger.isAfter && trigger.isUpdate) {
        for(Account account : trigger.new) {
            if(account.ParentId!=trigger.oldMap.get(account.Id).ParentId) {
                accountsWithUltimateParentUpdate.add(account);
            }
        }
    }

    /*
    *   If the parent is updated on some accounts,
    *   update the ultimate parent on these as well as
    *   on the child accounts in the hierarchy
    */
    if(!accountsWithUltimateParentUpdate.isEmpty()) {
        AccountTriggerHandler.updateUltimateParentOnChildAccounts(accountsWithUltimateParentUpdate);
    }
}

AccountTriggerHandler

/*
*       Author: Rahul Malhotra
*       Description: Trigger handler for Account trigger
*	Created Date:- 14-01-2022
*	Last Modified:- 19-01-2022
*       Code Origin:- SFDC Stop (https://www.sfdcstop.com)
*/
public with sharing class AccountTriggerHandler {

    /*
    *   Description: This method is used to update ultimate parent account on the current account
    *   as well as the child accounts present in the hierarchy
    */
    public static void updateUltimateParentOnChildAccounts(List<Account> accounts) {
        NAryTree tree = new NAryTree();
        IdCompare idCompare = new IdCompare();
        Account masterParentAccount = new Account(Name = 'MasterParentAccount');
        tree.insertData(masterParentAccount, NULL, NULL);
        for(Account account : accounts) {
            /*
            *   If an account's new parent is also updated, this account's ultimated parent account
            *   field should get updated automatically in the tree for the parent account.
            *   So, we don't need to keep it as a part of tree as it'll lead to duplicate nodes
            */
            if(
                account.ParentId==NULL ||
                tree.getRoot().getChildNodesMap()==NULL ||
                !tree.getRoot().getChildNodesMap().containsKey(account.ParentId)
            ) {
                tree.insertData(account, masterParentAccount, idCompare);
            }
        }
        Set<Id> accountIdSet = new Set<Id>(tree.getRoot().getChildNodesMap().keySet());
        accountIdSet.remove(null);
        while(!accountIdSet.isEmpty()) {
            List<Account> childAccounts = [SELECT Id, ParentId, Name FROM Account WHERE ParentId IN: accountIdSet];
            // * If there are no more accounts to process, break the loop
            if(childAccounts.isEmpty()) {
                accountIdSet.clear();
            }
            for(Account account : childAccounts) {
                // * If current child account is already present in the tree
                if(tree.getRoot().getChildNodesMap().containsKey(account.Id)) {
                    // * Getting current node
                    NAryTree.Node tempNode = tree.getRoot().getChildNodesMap().get(account.Id);
                    // * De-link current node from root node
                    tree.getRoot().getChildNodesMap().remove(account.Id);
                    // * Remove current node and it's subtree from the tree
                    tree.deleteTree(tempNode);
                }
                // * Inserting the child account in the tree
                tree.insertData(account, new Account(Id = account.ParentId), idCompare);
                // * Removing the parent account's id from the accountIdSet
                accountIdSet.remove(account.ParentId);
                // * Adding the child account's id to the set
                accountIdSet.add(account.Id);
            }
        }
        // * For debugging purposes - Printing the final tree
        tree.levelOrderPrint();
        // * Getting the root node from the tree and initial child nodes
        NAryTree.Node rootNode = tree.getRoot();
        Map<Id, NAryTree.Node> childNodesMap = rootNode.getChildNodesMap();
        // * Creating a list of accounts to update
        List<Account> accountsToUpdate = new List<Account>();
        // * Getting initial accounts with their parent information
        List<Account> accountsWithParentInformation = [SELECT Id, Parent.UltimateParentAccount__c FROM Account WHERE Id IN: childNodesMap.keySet()];
        // * Looping accounts
        for(Account account : accountsWithParentInformation) {
            // * Setting up ultimate parent account in the current account and it's descendants
            if(account.ParentId!=NULL) {
                account.UltimateParentAccount__c = account.Parent.UltimateParentAccount__c !=NULL ? account.Parent.UltimateParentAccount__c : account.ParentId;
                accountsToUpdate.addAll(updateUltimateParentByDFSOnCurrentSubtree(childNodesMap.get(account.Id), account.UltimateParentAccount__c));
            } else {
                account.UltimateParentAccount__c = NULL;
                accountsToUpdate.addAll(updateUltimateParentByDFSOnCurrentSubtree(childNodesMap.get(account.Id), account.Id));
            }
        }
        // * Adding current account to accounts to update list
        accountsToUpdate.addAll(accountsWithParentInformation);
        // * Updating accounts
        update accountsToUpdate;
    }

    /*
    *   Description: This method is used to update ultimate parent account id
    *   in all the nodes of a tree starting from the root node which is passed as a parameter
    */
    static List<Account> updateUltimateParentByDFSOnCurrentSubtree(NAryTree.Node root, Id ultimateParentAccountId) {
        // * Creating a queue to perform DFS and forming a list of accounts to update
        List<NAryTree.Node> accountNodesQueue = root.getChildNodesMap()?.values();
        List<Account> accountsToUpdate = new List<Account>();
        // * If account's queue is not NULL
        if(accountNodesQueue!=NULL) {
            // * Looping while queue is not empty
            while(!accountNodesQueue.isEmpty()) {
                // * Getting nodes at current level
                Integer nodesAtCurrentLevel = accountNodesQueue.size();
                // * Looping while nodes at current level is more than 0
                while(nodesAtCurrentLevel>0) {
                    // * Getting the current node and removing it from the queue
                    NAryTree.Node current = accountNodesQueue.get(0);
                    accountNodesQueue.remove(0);
                    // * Updating the ultimate parent account for the current account
                    // * and adding it to accounts to update list
                    Account currentAccount = (Account) current.getData();
                    currentAccount.UltimateParentAccount__c = ultimateParentAccountId;
                    accountsToUpdate.add(currentAccount);
                    // * Getting the child nodes for the current node and adding them to the queue
                    Map<Id, NAryTree.Node> childNodesMap = current.getChildNodesMap();
                    if(childNodesMap!=NULL) {
                        for(NAryTree.Node childNode : childNodesMap.values()) {
                            accountNodesQueue.add(childNode);
                        }
                    }
                    // * Decrementing nodes at current level by 1
                    nodesAtCurrentLevel--;
                }
            }
        }
        // * Returning the accounts to update list
        return accountsToUpdate;
    }
}

Happy Trailblazing..!!