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