Learning Data Structures: Trees

In this article we'll explore trees, a classic computer science data structure. Trees have many applications, used to organize information we interact with daily. Implementing the structure in our language of choice also gives us a chance to learn more about recursion.

In order to understand trees, we will learn what they are, how they are used, and how to implement them.

What are Trees?

The tree data structure is much like a tree in real life, they have roots and leafs. One key difference is that the data structure's root is at the top. Trees have other properties that make it a great way to organize the right body of information:

• Trees are hierarchical. More general things are near the top and more specific things are near the bottom. This helps organize data in a way that makes it easy to access it because at any layer we can choose which path to follow. Consider this diagram representing a book:

Note that the lower cells of this tree are all classified as a book but depending on how they're connected, they might be part of the first or second chapter. If you needed to quickly access the first sentence of a paragraph in Section 2, Chapter 2 of this book, you intuitively know to follow the path to the right and to ignore anything under Chapter 1.

• The children of one node are independent of the children of another node. Think about our book again, and imagine you want to delete all of Chapter 2. It sucks and you have to rewrite it 🙄. You can safely do so without affecting Chapter 1.

• Each leaf node is unique. You can count on every sentence of this book having a unique path from the top of our diagram to itself.

Trees in the Life of a Developer

Trees are a truly ubiquitous data structure. Here are some examples of trees that developers interact with all the time:

• The DOM: Web devs this one is for you! We write markdown for websites by nesting tags at different levels. In the end, we can visualize it like the book above:
  

• The UNIX file system: A lot of devs use a Mac or Linux operating system. These systems belong to the same family of operating systems. The way directories (folders) and files are organized is an example of a tree as well. Big, general directories like etc/ and bin/ are at the top right under the root / directory. Check it out by opening your terminal and running cd / followed by ls. Different parts of the system are categorized at different layers and there is a unique path to every file from root. Very commonly when using tools in the command line, you have to specify the path to a file for your program to use.

All the Technical Vocabulary

Here are all the words you should get familiar with to talk about trees effectively.

Node The smallest unit of a tree where data can be stored. A node has references to its children and a property to store data, commonly called it's "payload".

Edge Edges connect two nodes and represents the relationship between them. Every node except the root has exactly one incoming edge and any number of outgoing edges. In other words, every node except the root has one parent and any number of children.

Root The root of a tree sits at the top and has no incoming edges. We manipulate trees by first referencing the root.

Path A path is the set of nodes connected by edges, in order from one node to one of it's descendants.

Children The set of nodes that have incoming edges from the same node p are children of p.

Parent A node p is a parent to all the nodes to which p is connected to by outgoing edges.

Sibling Nodes that share the same parent are siblings of one another. They share the origin of their single incoming edge.

Subtree A subtree is a set of nodes and edges consisting of a parent node and all its descendants. Internalizing this definition helps think about trees in a recursive way which is key to a lot of algorithm problems.

Leaf Node A leaf is a node with no children.

Level The level of a node is equals to the amount of edges from root to that node.

Height The height of a tree is equals to the greatest level of any node in the tree.

Defining a Tree

Lets bring all we've explored together to formulate a definition of a tree.
Nodes and Edges A tree is a set of nodes connected by a set of edges and meet these properties:

• One node is designated the root node
• Every node n, except the root node, is connected by an incoming edge from exactly one other node p, where p is the parent of n.
• There is a unique path from the root node to each node
• If each node in the tree has a maximum of two children, the tree is a binary tree.

Implementing a Tree

A quick way to implement a tree is to define a Node structure that will allow us to connect it to other instances of itself in the way we knows trees connect. For simplicity, this will be a binary tree.

class Node {
  constructor (value) {
    this.payload = value
    this.leftChild = null
    this.rightChild = null
  }
}

With the code above, we can instantiate some Nodes and connect them to form a tree.

const a = Node('A');
a.leftChild = Node('B');
b.rightChild = Node('C');

The children of a, for which we didn't assign a variable, can still be accessed and can become parents themselves.

a.leftChild.leftChild = Node('D');

We can also define this data structure recursively, meaning a we use a Node to define Node 🤔

class Node {
  constructor (value, leftChild = null, rightChild = null) {
    this.value = value
    this.leftChild = leftChild
    this.rightChild = rightChild
  }
}

I used the Stones to destroy the Stones.

• Thanos

And we can use it like so!

const numbersTree = Node(1, 
  Node(2, Node(4)), 
  Node(3, Node(5)));

Try and draw this tree!

Conclusion

Trees are a versatile and prominent data structure. I hope you feel more equipped to talk about trees and that these examples have illustrated some mental models that you will need to know trees closely. The more familiar we get with our data structures, the better we are able to leverage them in real world problems.

Share thoughts, feedback, and your own implementations of nodes or trees in the comments below! Thanks for reading!

Cover photo by Skitterphoto from Pexels