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 we will look at implementing a tree data structure in Javascript; lets get into it.
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, 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.
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.
Tree Terminologies
Some of the terms used to describe the relationship between nodes in a tree are:
Parent and Child
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].
Sibling
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].
Leaf
A node with no child nodes is called a leaf node. Nodes [5, 6, 7, 8, 9, 10] are all leaf nodes.
Ancestor and Descendant
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.
Subtree
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.
Height Of A Tree
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.
Depth Of A Node
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.
Types Of Tree Data Structure
There are a lot of tree type data structures, but we are just going to look at a few.
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.
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 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.
if you would like to know what other tree type data structures there are check out this article.
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.
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.
