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.

Data Structures in JavaScript Part 2 : Doubly-linked list

This is a continuation from my last blog on linked lists. Last post was about a singly linked list, so if you have not read that post, you should read that before reading this post.

First lets get down to the definition of a doubly-linked list. As always, this definition is taken directly from Wikipedia (no sense in reinventing the wheel) - "In computer science, a doubly-linked list is a linked data structure that consists of a set of data records, each having two special link fields that contain references to the previous and to the next record in the sequence. It can be viewed as two singly-linked lists formed from the same data items, in two opposite orders."

Lets get started with some code. First create three objects called a, b and c.

var a = {value : "a", nextNode : "b", previousNode : ""};

var b = {value : "b", nextNode : "c", previousNode : "a"};

var c = {value : "c", nextNode : "", previousNode : "b"};

You will notice that these objects look very similar to what we created in the singly linked list demo, but we have added a new property called "previousNode". As you would expect, the previous Node works just like nextNode, except it contains the previous node in the sequence of nodes, and "a" has no previous node since it's the the beginning of the sequence.

Now lets write a function. First I want to traverse through our nodes from first to last. We will use the same method that we used in the singly linked list, but this time we will call it "sortListAsc".

var sortListAsc = function (obj) {

var nodeString = obj.value, nextNode = obj.nextNode;

while (nextNode != "") {

nodeString += ", " + this[nextNode].value;

nextNode = this[nextNode].nextNode

}

return nodeString;

}

And then we call the method like this:

sortListAsc(a);

We passed the "a" object to the method and from there the method takes over and is able to gather all the objects and print out the sequence in which they appear.

Now what if we want to start from the last element in the sequence and traverse to the front? That's where the doubly-linked list comes into play. We are able to start from the back of the list since we now know the previous node. Lets look at the code; we will call this method "sortListDesc".

var sortListDesc = function (obj) {

var nodeString = obj.value, previousNode = obj.previousNode;

while (previousNode != "") {

nodeString += ", " + this[previousNode].value;

previousNode = this[previousNode].previousNode

}

return nodeString;

}

At first glance these methods look identical, and they are with the exception that the while loop is looking for the previousNode instead of the next node. Here is how we would execute that function:

sortListDesc(c);

We passed in the "c" object to the method and from there the method takes over and is able to gather all the objects and print out the sequence in which they appear, and in this case it's from back to front.

And that pretty much sums up a doubly-linked list. Please feel free to comment or ask any questions.