Data Structures: Trees I
Tags: beginners, computerscience, webdev, programming
Published: 2022-05-08 09:02:03

This 2-part article will be on Tree data structures. In this first part we are going to look at what a tree data structure is, types of tree data structures, and some applications/use cases of tree data structures. In the [second part](https://dev.to/m13ha/data-structures-trees-ii-4kng) we will look at implementing a tree data structure in Javascript; lets get into it.


![root meme](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/lolxr50mxeeh4uor8kpa.jpg)

<p>&nbsp;</p>

###Trees

A tree is a non-linear data structure that is used to store hierarchal data, e.g. a family tree, a company employee structure.  Similar to [Linked Lists](https://dev.to/m13ha/data-structures-linked-list-i-312k), a Tree is made up of nodes that store a value and pointers to other related nodes. Trees make it fast to retrieve and organize data on a computer.

<p>&nbsp;</p>

### Structure Of A Tree Data Structure

All Trees have a node at the top known as the root; all other nodes are descendants of the root node.

![Root node image](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1ht4722ju9b37rzuokrk.png)
 
<p>&nbsp;</p>

#### Tree Terminologies

Some of the terms used to describe the relationship between nodes in a tree are:

<p>&nbsp;</p>

#### Parent and Child


![parent node tree data structure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kwgbl8f9qxc961fjd8yc.png)

A parent node refers to the node that directly precedes another node. In the above image we can see that **node [2]** is a parent of **nodes [5, 6, 7]**, which would also make **nodes [5,6,7]** children / child nodes of **node [2]**. similarly, **nodes [9, 10]** are children of **node [4]** and **node [3]** is the parent of **node [8]**. 

<p>&nbsp;</p>

#### Sibling

![sibling nodes](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kpr6t1ksrhwdksal7uoq.png)

Nodes that share a parent node are referred to as siblings. Note all nodes in a tree can only have 1 parent except the root node which has no parent. In the above image we can see that **nodes [5, 6, 7]** are siblings; so are **nodes [9, 10]**.

<p>&nbsp;</p>

#### Leaf


![Leaf node](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/no8l0w3xu13eeno0ae84.png)

A node with no child nodes is called a leaf node. **Nodes [5, 6, 7, 8, 9, 10]** are all leaf nodes.

<p>&nbsp;</p>

#### Ancestor and Descendant


![ancestors and descendants in tree data structure](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q1mo5udvxvisjxofj2r1.png)

An ancestor of a node refers to nodes that share a direct reverse connection between a given node and the root node; you can think of them as grand parents. In the above image we can see that **nodes [6, 2, 1]** are ancestors of **node [11]**, though **node [6]** is technically an ancestor of node [11] it is more clear to call it a parent node.

Descendants are the same principle, but backwards. **Node [11]** is a descendant of **nodes [6, 2, 1]**. As we mentioned before, all nodes are descendants of **nodes [1]** aka the root nodes.

<p>&nbsp;</p>

#### Subtree 


![Subtree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/g3j2he5wa7bqpqdfojsa.png)

Any node in a tree that has descendants can be considered a subtree. All subtrees are descendants of the root node e.g. **node [2]** and it's child nodes.

<p>&nbsp;</p>

#### Height Of A Tree


![Height of node](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ps2a9m91hcv7eb3omru0.png)


The height of a tree refers to the number of nodes/edges between the root node and its last descendants or farthest leaf nodes. The height of the above tree is **3**.

<p>&nbsp;</p>

#### Depth Of A Node


![Depth of a node](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vvnan2tjlkgxgu4ks82a.png)


The depth of a node refers to the number of nodes/edges between a given node and the root node. In the above image, the depth of **node [10]** is **2**.

<p>&nbsp;</p>

### Types Of Tree Data Structure

There are a lot of tree type data structures, but we are just going to look at a few.

<p>&nbsp;</p>

#### General Tree

A general tree is a tree that has no restrictions on the number of child nodes a parent node can have, including the root node.

![general tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0blbm7b1jn9g44xa3zd6.png)

<p>&nbsp;</p>

#### Binary Tree

A binary tree is a tree whose nodes can have no more than 2 child nodes per parent node including the root node. The child nodes in a binary tree are called left and right child

![Binary tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8ynvyp65fs17bpm8kj5h.png)

<p>&nbsp;</p>

#### Binary Search Tree (BST)

A BST is a tree whose nodes are sorted when created. The nodes are sorted based on whether they are greater than or less than their parent node. Nodes greater than their parent node are placed to the right, while nodes less than are placed to the left.


![binary search tree](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i27z4uxhl4l1z34kr9k3.png)

<p>&nbsp;</p>

if you would like to know what other tree type data structures there are check out this [article.](https://towardsdatascience.com/8-useful-tree-data-structures-worth-knowing-8532c7231e8c)

<p>&nbsp;</p>

### Uses/Application Of Tree Data Structures

- Trees are used in computer file systems to keep track of folder structure.

- BST are often used in search and sorting algorithms.

- Domain name space (DNS) uses tree data structures to manage domain names.

- Trees are used when rendering computer graphics.

- Dictionary applications, autocomplete and spell check use trees.

<p>&nbsp;</p>

Trees are a very complex data structure, so if you have any questions please leave a comment and i will try my best to answer it. In the next part of this article we will look at how to create a BST in Javascript. Thank you for reading.

[Part 2](https://dev.to/m13ha/data-structures-trees-ii-4kng)

![see you later](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ey5vwrco1z6mhlu27dfg.gif)