I Speak for the Trees
Tags: computerscience, 100daysofcode
Published: 2020-10-13 04:17:00

Trees are similar to linked lists in that they are made up of nodes and links. There are certainly some differences between the two though. Let’s find out what makes a tree a tree.

## What is a Tree?

In my previous post I discussed [arrays and linked lists](https://www.danielleskosky.com/linked-lists/). Arrays and linked lists are **linear data structures**. They are only able to be traversed sequentially. Trees are a bit different. They are **non-linear data structures**. Non-linear data structures are not organized sequentially like linear data structures are, so it only makes sense that they have to be traversed non-sequentially.

Don’t worry though. This post will not focus on the traversal of trees. Instead, let us make sure that we know what a tree is.

## Some Key Terms

Let us start by becoming familiar with some key terms.

* **Nodes:** Hold data

* **Root:** Uppermost node of tree

* **Link/Edge:** The connection between a Parent Node and a Child Node

* **Parent Node:** A node which is connected to one or more nodes on the lower level (Child Nodes)

* **Child Node:** A node which is linked to an upper node (Parent Node)

* **Sibling Node:** Nodes that have the same Parent Node

* **Leaf Node:** A node that doesn’t have any Child Node

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/w41tuya65za8his055no.png)

Using the above figure, let’s go over some of these terms that we have just learned. **A** is the **root** node. **A** is also the **parent** node to **child** nodes **B**, **C**, and **D**. Node **C** is a **parent** node to **child** nodes **E** and **F**. Nodes **B**, **C**, and **D** share the same **parent** node **A**. This makes them **sibling** nodes. The same is true for nodes **E** and **F**. They are sibling nodes because they both have node **C** as a parent. Finally, nodes **B**, **D**, **E**, and **F** are **leaf** nodes as they do not have any **child** nodes.

## Some More Key Terms

Here are a few more key terms that are helpful for when talking about trees.

* **Sub-tree:** A sub-tree is a section of the main tree. Pick a node from a tree. That node and all of the nodes below it is a sub-tree.

* **Depth:** The distance that a node is from the root node. The easiest way to find the depth is to start at the root node and then count the number of edges that exist between a certain node and the root.

* **Height:** Start at a node. Count the number of edges that exist between the node and its furthest removed leaf node. This is the height.

![](https://cdn-images-1.medium.com/max/2378/0*sTvu6_mhUiP9wfMX.png)

The figure above shows the **depths** and **heights** for the different nodes. Each circled section represents a different **sub-tree**. There are a total of six different **sub-trees**.

## Types of Trees

This post isn’t going to go into too much detail about the different types of trees. However, it is still a good idea to at least become familiar with some different types of trees that are commonly used.

Ok, let’s at least talk about N-ary Trees for a bit. Think of **N** simply as the number that describes the parent node with the most children. For example, look at the first figure. Node **A** has the most children. It has **3**. **N** is **3**. That makes it a **3-ary** tree. Let’s go the next figure. There isn’t any one node in particular that has the most children. **BUT,** the most children that any one node has is **2**. **N** is **2**. This makes it a **2-ary** tree. Or more commonly known as a **Binary Tree**.

## Where are Trees Used?

At this point, you are probably wondering where trees are actually used. Here is a tree structure for you: folders. That’s right, kind of mind blowing right?! When you navigate up and down through directories you are in some respects traversing a tree structure. So, next time you are at a party, be sure to tell your friends that you traverse tree structures on the regular. They will think you are wicked smart.

Or how about this one. I have recently been learning about React, so you can be sure that I was pretty surprised when I learned that the [DOM](https://en.wikipedia.org/wiki/Document_Object_Model) is, in fact, a tree structure.
> *“The Document Object Model (DOM) is a cross-platform and language-independent interface that treats an XML or HTML document as a tree-structure wherein each node is an object representing a part of the document.”*

Do some digging yourself (I had to do at least one pun, sorry). I think you will find that trees are all around us in the great big world of programming!