Converting a Tree to a List in JavaScript

With the meteoric rise of JavaScript MVC frameworks, data structures and algorithms long handled server-side are now managed on the client. JavaScript references objects thru memory addresses, making linked lists, trees, even graphs all possible to build and traverse. So dust off the old computer science textbook, grab a cup of coffee and whiteboard pen, and check out this interesting problem I encountered a couple months ago.

Scenario: The 3rd party web service your app consumes generates JSON in a tree structure with data values in the leaf nodes (example below). You need to convert these tree leaf nodes to a list for Angular’s ng-repeat to iterate over in your View. Not only must the nodes’ ordering be maintained, but any duplicate nodes should be removed.

Question: How can we convert a tree’s leaf nodes into a list while preserving order and removing the duplicates? We’ll analyze it using Big-O notation for time complexity.

In this N-ary tree a single tree node can have any number of child nodes. In designing for scalability think of this tree as having 1,000,000 leaf nodes.

In our example a node is an object with two properties:

1. a string data property
2. an array holding child nodes.

A leaf node will have a non-null data property and null children property.

{
    data: 'A',
    children: null
}

A non-leaf node is the inverse, with a null data value and an non-null children array of objects.

Here’s sample JSON

{
    data: null,   // non-leaf node
    children: [
        {
            data: 'A',   // leaf node
            children: null
        },
        {
            data: 'B',   // leaf node
            children: null
        },
        {
            data: null,   // non-leaf node
            children: [
                {
                    data: 'C',   // leaf node
                    children: null
                },
                {
                    data: 'A',   // leaf node
                    children: null
                },
            ]
        }
    ]
}

Let’s dig in.

A brute force approach would be to do a pre-order traversal thru the tree. At each node visit iterate thru the array and insert the leaf node in order in the list if not a duplicate.

Time complexity

1. Pre-order traversal - O(n)
2. For each visit, iterate thru the array and insert a leaf node in order - O(n) inside O(n)

This results in O(n² + n) which after refactoring is O(n²). There’s probably a better way.

A hashing solution uses an object literal as a hashMap to detect duplicates.

1. Use a pre-order traversal to visit each node
2. For each visit
   
   • check if the node data value is already in the hashMap. If so, it’s a duplicate and can be overlooked. If not assign the node into the array.
     
   • append the node to the end of the array.

1) Pre-order tree traversal

/**
*  Pre-order tree traversal visits each node using stack. 
*  Checks if leaf node based on children === null otherwise 
*  pushes all children into stack and continues traversal. 
*  hashMap object literal used for deduping.
*  @param root - deserialized JSON root to begin traversal
*  @returns array  - final array of nodes in order with no dups
*/
function convertTreeToList(root) {
    var stack = [], array = [], hashMap = {};
    stack.push(root);

    while(stack.length !== 0) {
        var node = stack.pop();
        if(node.children === null) {
            visitNode(node, hashMap, array);
        } else {
            for(var i = node.children.length - 1; i >= 0; i--) {
                stack.push(node.children[i]);
            }
        }
    }

    return array;
}

2) Node visit

/**
*  For each node visit if node not a hashMap key, insert 
*  into array.  Then append node into end of the array.
*  @params node - object to check
*  @param hashMap - object literal used for deduping
*  @param array - final array that nodes are inserted
*/
function visitNode(node, hashMap, array) {
    if(!hashMap[node.data]) {
        hashMap[node.data] = true;
        array.push(node);
    }
}

Time Complexity

1. preOrder() - O(n)
2. for each visit
   
   • check if node data is already in hashMap - O(1)
   • insert the node into the array - O(1)

O(n + 1 + 1) evaluates to only O(n) after refactoring. The first unique node is kept and the order of the leaf nodes are maintained.

CodePen for Converting Tree to List

Can you beat it? Any ideas? I’d enjoy your feedback. Feel free to reach out on
LinkedIn.