Introduction to Tree Data Structure

So we have arrived now at our next stop in the series of “Understanding Data Structure and Algorithms with JavaScript 🚀”, which is the Tree data structure. Unlike data structures, like an array, stack, LinkedList, or queues which stores data in a linear way, a tree data structure stores data non-linear way. In a Tree, data is arranged in hierarchal order, somewhat representing a tree-like structure.

In this blog, we will understand more about Tree, their importance, some important terminologies, types of trees, and their advantages.

What is a Tree Data Structure?

A Tree data structure is a non-linear data structure where data is arranged in a hierarchical pattern and represents a tree-like structure. It consisted of different nodes which are interlinked with each other at multiple levels.

Each node consists of data and links to the different nodes which are known as children. Tree’s data structure plays important role in nonlinear data structure arrangement, which ensures a faster response time during a search query.

Also read, What is Big O Notation – Space and Time Complexity

Why Tree Data Structure is so Important

There are many ways Tree data structure plays an important role:-

• One of the biggest disadvantages of using linear data structures like an array or a LinkedList is the total time taken to search an item. Since both are linear data structures they require linear time to search any element.
• A tree is a nonlinear data structure thus it does not store data in a linear sequential manner. It follows the hierarchical pattern of data collection.
• Due to the nonlinear nature of tree structure, this allows for faster search response and better convenience in managing or storing data.
• Tree data structures are mostly applied in managing a file system of any device. It enhances the data storing, accessing, and deletion process.

Also read, Does College Make You a Better Coder?

Important Terminology related to Tree Data Structure

Here are some important terminologies related to Tree Data Structure:-

• Node:- A node is the basic unit of a tree data structure that contains data and references to another node.
• Root:- Root is the topmost and head node of the tree. A tree can only have one root.
• Edge:- The links which connect two nodes are known as Edge. For the n number of nodes in a tree, there are n-1 edges.
• Levels:- Levels are each step from top to bottom of the tree. The root is at level 0, the children of the root are at level 1 and then their children are at level 2.
• Path:- Path is referred to the sequences of nodes along the edges of the tree.
• Leaf:- Leaf is a node that does not have any child node.
• Parent:- A node through other nodes emerges is known as the Parent node.
• Child:- A node which is emerged from another node is known as a Child node. Every other node except Root is a child node.
• Sibling:- Nodes having the same parents is known as siblings.
• Sub-tree:- Set of a node that has parent and child node together is known as Sub-tree.
• Degree:- Total number of children of a node is known as Degree. A leaf that has no children is said to have zero degrees.
• Internal Node:- A node that has at least one child node is known as an internal node. All the other nodes except the leaf node are said to be Internal nodes.

Also read, Easy Explanation of Linked list Data Structure in JavaScript

Different types of Tree Data Structures

General Tree

A General Tree data structure is a tree that does not have any pre-defined configuration or limitations. Thus, any tree with a hierarchical structure can be characterized as a general tree.

Binary Tree

A Binary tree is a tree that only has two nodes aka children, thus it is called a “Binary Tree’. In a Binary tree, any node can have 0,1 or two nodes only.

Binary Search Tree

A binary Search Tree is a subset of a Binary tree that is configured in such a way that it allows for faster searching, insertion, and deletion of data.

• the left subtree has values lower than the parent node.
• the right subtree has values greater than the parent node.
• each subtree of BST is it is own binary search tree.

AVL Tree

AVL Tree or Adelson-Velsky-Landis, is named after its creator Adelson-Velsky and Landis. AVL Tree is also known as a self-balancing tree where each node cannot have more than two children/nodes and the height difference between left and right child cannot be more than 1 for all the nodes.

Red Black Tree

Red Black Tree is very similar to AVL Tree which also has height-balanced characteristics. Each node of the tree consists of an extra bit, representing a color (red or black). These colors ensure that the tree remains balanced during insertion and deletions.

Also read, Simple Explanation of Stack and Queue with JavaScript

Advantages of using Tree Data Structures

• The tree data structure provides a hierarchical way of storing data.
• It reflects a non-linear structural relationship in a data set.
• The tree data structure also allows the insertion, deletion, and searching operations to be faster than on an array or linked list.
• The tree also provides a more flexible and easy way to assemble and move data.