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. 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

Using the above figure, let’s go over some of these terms that we have just learned. **A** is the **r****oot** 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.

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.

- N-ary Tree
- Balanced Tree
- Binary tree
- Binary Search Tree
- AVL Tree
- Red-Black Tree
- 2-3 Tree

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 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!