Tree Data Structure in JavaScript
A tree data structure is a graph without any cycles. I can hear you saying, "Kyle, that's a super helpful explanation," with a healthy dose of sarcasm already. "No cycles" means that no three nodes create a circuitous path. In a tree, nodes have a single parent node and may have many children nodes. They never have more than one parent nor point to any siblings.
The most common tree structure you see is a web page. The underlying structure is often called the "DOM tree". The html element forms the root of our tree, with children of head and body, so on and so forth. In this lesson, we'll create a quick example of a DOM tree with our tree data structure.
Instructor: [00:00] A tree is a graph without any cycles. A cycle is when three or more nodes are connected in a circuitous path. Tree nodes, instead of having neighbors and no hierarchy like a graph, might be thought of having children and are hierarchical.
[00:16] Each node can contain many children. Node children may have an edge between them, and they may not be connected to any other parent node. To write our tree data structure, we'll start by creating a function to create our nodes.
[00:31] Each node receives a key as an argument. We'll return that key in the object returned by the factory function. Next, a tree node can have many children, so we'll create an array and return that reference.
[00:44] Lastly, we'll add a method called add child so that we can add children to this node. Add child will receive a key as an argument, create the node, push it to the children array, and return that node.
[00:58] Now we can create our tree factory function. Trees must have a root node, so we'll expect the root key to be passed as an argument when the tree is created. We'll use this key to create a node, and we'll assign it to root and return it in our tree object.
[01:15] This tiny object is all we need to begin to use our tree, since each node contains in it the ability to add nodes to it. Perhaps the most common tree structure web developers deal with on a regular basis is the dom tree. The HTML of every page on the web is a tree structure.
[01:34] We can create the basic layout of a page pretty quickly with our tree. I'll create a tree and name it dom, giving it the root key of HTML. Our HTML node adds two children, head and body.
[01:49] Our head node receives one child, our title. Our body node likely has many elements. In our case, we'll give it a header, a main, and footer. Our header probably has an H1. Our main perhaps has a paragraph. Our footer might have the copyright year.
[02:14] Now that we have our tree structure, it might be nice to visualize it. Let's create a print method that traverses our tree and logs out each node's key. I want to return a string from our print method, and I'll be concatenating onto this string with each level we traverse through our tree.
[02:30] I'm going to create a variable called result, and I will return that. I'm going to create a traverse function that we'll call recursively on our nodes. Traverse will accept three arguments, the node it's operating on, a visiting function to fire on each node, and a depth argument I'm going to use for my output.
[02:49] Depth isn't necessary in this implementation and could be derived from the data, but this will be useful for the lesson. Now, we start by visiting our current node. Then, if the node has any children, we want to traverse through each one of them, passing them same visiting function but increasing the depth by one.
[03:09] Now I'll create a function to pass as our visiting function. This function will mutate our result string. For the very first node key, I only want to return the key. For every subsequent key, I want to create a new line and then add twice as many spaces as the depth before each node key.
[03:30] This will give a nice nested layout to our output. Next, I want to traverse starting from the root node and passing our visiting function and a depth of one. Now that our print method is complete, let's call it on the dom tree we created before. We need to create a little more room in our terminal so we can see the full visualization. There you can see our dom tree printed out.