Data Structures in JavaScript Part 3 : Tree Struct

There's a bunch of different ways to setup a tree structure, so I wanted to setup the most simple version I could. This is not the most efficient way to setup and display a tree, but for small data sets, it will work just fine.

First off, lets define what a tree is. "A Tree structure is a way of representing the hierarchical nature of a structure in a graphical form. In computer science, a tree is a widely-used data structure that emulates a hierarchical tree structure with a set of linked nodes." - Wikipedia

Now lets setup our tree structure:

var tree = {

a : {value : "This is node A", parent : ""},

b : {value : "This is node B", parent : "a"},

c : {value : "This is node C", parent : "a"},

d : {value : "This is node D", parent : "c"},

e : {value : "This is node E", parent : "c"},

f : {value : "This is node F", parent : "c"}

}

Like I mentioned before, this is a very inefficient tree structure because it will have to be traversed for each node to find the relationship. A hash may be a faster solution, but we can look at other options in the next post to see how we can optimize and be more efficient.

You will notice that each node has a parent node. Nodes can have many children, but only one parent. The parent signifies who the parent object is in the hierarchy.

Now lets build a function to traverse the tree and print out the tree in a viewable format.

var buildTree = function (obj, node) {

    var treeString = "<ul><li>" + obj[node].value;

        for (var i in obj) {

            if (obj[i].parent == node) {

                treeString += buildTree(obj, i);					

            }

        }

        treeString += "</li></ul>";

        return treeString;

    }

As you can see we are passing in "obj", which is our tree structure and "node" is the first node we want to traverse. Ideally we should be able to pass in nothing for "node" and it will traverse the tree, but in this example we want to pass in the starting node.

Looking at the for loop, you will notice that we loop through the tree for each iteration of the node, which is a very slow process, but since our dataset is tiny, performance is not a concern. You will notice in the loop that we are using recursion, make sure to read about recursion if you are not familiar with it. My favorite explanation of recursion is "In order to learn recursion, you must first learn recursion".

Now call the function and see the output:

buildTree(tree, "a");

you should see the following output:

• This is node A
  • This is node B
• This is node C
  • This is node D
  • This is node E
• This is node F

As you can see the method printed out the tree based on it's parent/child relationship. Try altering the parent relationship and see how easily you can restructure the hierarchy of the tree.