Trees are well-known as a non-linear data structure. They don’t store data in a linear way. They organize data hierarchically.A tree is a collection of entities called nodes. Nodes are connected by edges. Each node contains a value or data, and it may or may not have a child node .

Data Trees: Definition

<ul><li>Root is the topmost node of the tree  </li><li>Edge is the link between two nodes  </li><li>Child is a node that has a parent node  </li><li>Parent is a node that has an edge to a child node  </li><li>Leaf is a node that does not have a child node in the tree  </li><li>Height is the length of the longest path to a leaf  </li><li>Depth is the length of the path to its root  </li></ul>

Terminology summary

Eventually, you will learn about hash tables too. If you are pursuing a Computer Science degree, you have to take a class on data structure. You will also learn about linked lists, queues, and…

computerscience

Computer Science

This post was originally published at <a href="https://leandrotk.github.io/tk/2020/02/tree-data-structure/index.html">TK’s Blog </a>.

When you first learn to code, it’s common to learn arrays as the “main data structure.”

Eventually, you will learn about <code>hash tables </code>too. If you are pursuing a Computer Science degree, you have to take a class on data structure. You will also learn about <code>linked lists </code>, <code>queues </code>, and <code>stacks </code>. Those data structures are called “linear” data structures because they all have a logical start and a logical end.

When we start learning about <code>trees </code>and <code>graphs </code>, it can get really confusing. We don’t store data in a linear way. Both data structures store data in a specific way.

This post is to help you better understand the Tree Data Structure and to clarify any confusion you may have about it.

<ul><li>What is a tree </li><li>Examples of trees </li><li>Its terminology and how it works </li><li>How to implement tree structures in code. </li> </ul>

Let’s start this learning journey. :)

When starting out programming, it is common to understand better the linear data structures than data structures like trees and graphs.

Trees are well-known as a non-linear data structure. They don’t store data in a linear way. They organize data hierarchically.

What do I mean when I say in a hierarchical way?

Imagine a family tree with relationships from all generation: grandparents, parents, children, siblings, etc. We commonly organize family trees hierarchically.

The above drawing is is my family tree. <code>Tossico, Akikazu, Hitomi, </code>and <code>Takemi </code>are my grandparents.

<code>Toshiaki </code>and <code>Juliana </code>are my parents.

<code>TK, Yuji, Bruno </code>, and <code>Kaio </code>are the children of my parents (me and my brothers).

An organization’s structure is another example of a hierarchy.

In HTML, the Document Object Model (DOM) works as a tree.

The <code>HTML </code>tag contains other tags. We have a <code>head </code>tag and a <code>body </code>tag. Those tags contains specific elements. The <code>head </code>tag has <code>meta </code>and <code>title </code>tags. The <code>body </code>tag has elements that show in the user interface, for example, <code>h1 </code>, <code>a </code>, <code>li </code>, etc.

A <code>tree </code>is a collection of entities called <code>nodes </code>. Nodes are connected by <code>edges </code>. Each <code>node </code>contains a <code>value </code>or <code>data </code>, and it may or may not have a <code>child node </code>.

The <code>first node </code>of the <code>tree </code>is called the <code>root </code>. If this <code>root node </code>is connected by another <code>node </code>, the <code>root </code>is then a <code>parent node </code>and the connected <code>node </code>is a <code>child </code>.

All<code>Tree nodes </code>are connected by links called <code>edges </code>. It’s an important part of <code>trees </code>, because it’s manages the relationship between <code>nodes </code>.

<code>Leaves </code>are the last <code>nodes </code>on a <code>tree. </code>They are nodes without children. Like real trees, we have the <code>root </code>, <code>branches </code>, and finally the <code>leaves </code>.

Other important concepts to understand are <code>height </code>and <code>depth </code>.

The <code>height </code>of a <code>tree </code>is the length of the longest path to a <code>leaf </code>.

The <code>depth </code>of a <code>node </code>is the length of the path to its <code>root </code>.

<ul><li>Root is the topmost <code>node </code>of the <code>tree </code> </li><li>Edge is the link between two <code>nodes </code> </li><li>Child is a <code>node </code>that has a <code>parent node </code> </li><li>Parent is a <code>node </code>that has an <code>edge </code>to a <code>child node </code> </li><li>Leaf is a <code>node </code>that does not have a <code>child node </code>in the <code>tree </code> </li><li>Height is the length of the longest path to a <code>leaf </code> </li><li>Depth is the length of the path to its <code>root </code> </li> </ul>

Now we will discuss a specific type of <code>tree </code>. We call it the<code>binary tree </code>.

“In computer science, a binary tree is a tree data structure in which each node has at the most two children, which are referred to as the left child and the right child.” — <a href="https://en.wikipedia.org/wiki/Binary_tree">Wikipedia </a>

So let’s look at an example of a <code>binary tree </code>.

The first thing we need to keep in mind when we implement a <code>binary tree </code>is that it is a collection of <code>nodes </code>. Each <code>node </code>has three attributes: <code>value </code>, <code>left_child </code>, and <code>right_child </code>.

How do we implement a simple <code>binary tree </code>that initializes with these three properties?

Here it is. Our <code>binary tree </code>class.

When we instantiate an object, we pass the <code>value </code>(the data of the node) as a parameter. Look at the <code>left_child </code>and the <code>right_child </code>. Both are set to <code>None </code>.

Because when we create our <code>node </code>, it doesn’t have any children. We just have the <code>node data </code>.

We can pass the <code>string </code>‘<code>a </code>’ as the <code>value </code>to our <code>Binary Tree node </code>. If we print the <code>value </code>, <code>left_child </code>, and <code>right_child </code>, we can see the values.

Let’s go to the insertion part. What do we need to do here?

We will implement a method to insert a new <code>node </code>to the <code>right </code>and to the <code>left </code>.

<ul><li>If the current <code>node </code>doesn’t have a <code>left child </code>, we just create a new <code>node </code>and set it to the current node’s <code>left_child </code>. </li><li>If it does have the <code>left child </code>, we create a new node and put it in the current <code>left child </code>’s place. Allocate this <code>left child node </code>to the new node’s <code>left child </code>. </li> </ul>

Again, if the current node doesn’t have a <code>left child </code>, we just create a new node and set it to the current node’s <code>left_child </code>. Or else we create a new node and put it in the current <code>left child </code>’s place. Allocate this <code>left child node </code>to the new node’s <code>left child </code>.

And we do the same thing to insert a <code>right child node </code>.

But not entirely. We still need to test it.

Let’s build the following<code>tree </code>:

To summarize the illustration of this tree:

<ul><li><code>a </code><code>node </code>will be the <code>root </code>of our <code>binary Tree </code> </li><li><code>a </code><code>left child </code>is <code>b </code><code>node </code> </li><li><code>a </code><code>right child </code>is <code>c </code><code>node </code> </li><li><code>b </code><code>right child </code>is <code>d </code><code>node </code>(<code>b </code><code>node </code>doesn’t have a <code>left child </code>) </li><li><code>c </code><code>left child </code>is <code>e </code><code>node </code> </li><li><code>c </code><code>right child </code>is <code>f </code><code>node </code> </li><li>both <code>e </code>and <code>f </code><code>nodes </code>do not have children </li> </ul>

So here is the code for the <code>tree </code>:

Now we have to think about <code>tree </code>traversal.

We have two options here: Depth-First Search (DFS) and Breadth-First Search (BFS) .

<ul><li>DFS “is an algorithm for traversing or searching tree data structure. One starts at the root and explores as far as possible along each branch before backtracking.”— <a href="https://en.wikipedia.org/wiki/Depth-first_search">Wikipedia </a> </li><li>BFS “is an algorithm for traversing or searching tree data structure. It starts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.”— <a href="https://en.wikipedia.org/wiki/Breadth-first_search">Wikipedia </a> </li> </ul>

So let’s dive into each tree traversal type.

DFS explores a path all the way to a leaf before backtracking and exploring another path. Let’s take a look at an example with this type of traversal.

The result for this algorithm will be 1–2–3–4–5–6–7.

<ol><li>Start at the <code>root </code>(1). Print it. </li> </ol>

2. Go to the <code>left child </code>(2). Print it.

3. Then go to the <code>left child </code>(3). Print it. (This <code>node </code>doesn’t have any children)

4. Backtrack and go the <code>right child </code>(4). Print it. (This <code>node </code>doesn’t have any children)

5. Backtrack to the <code>root </code><code>node </code>and go to the <code>right child </code>(5). Print it.

6. Go to the <code>left child </code>(6). Print it. (This <code>node </code>doesn’t have any children)

7. Backtrack and go to the <code>right child </code>(7). Print it. (This <code>node </code>doesn’t have any children)

When we go deep to the leaf and backtrack, this is called DFS algorithm.

Now that we are familiar with this traversal algorithm, we will discuss types of DFS : <code>pre-order </code>, <code>in-order </code>, and <code>post-order </code>.

This is exactly what we did in the above example.

<ol><li>Print the value of the <code>node </code>. </li><li>Go to the <code>left child </code>and print it. This is if, and only if, it has a <code>left child </code>. </li><li>Go to the <code>right child </code>and print it. This is if, and only if, it has a <code>right child </code>. </li> </ol>

The result of the in-order algorithm for this <code>tree </code>example is 3–2–4–1–6–5–7.

The left first, the middle second, and the right last.

<ol><li>Go to the <code>left child </code>and print it. This is if, and only if, it has a <code>left child </code>. </li><li>Print the <code>node </code>’s value </li><li>Go to the <code>right child </code>and print it. This is if, and only if, it has a <code>right child </code>. </li> </ol>

Everything you need to know about tree data structures

Data Trees: Definition

Terminology summary

Sarah Kelly's ideas are part of this journey:

Related collections

Similar ideas