Tree Data Structure and its Applications

What is Tree Data Structure?

A tree is a non-linear data structure as it stores data in a hierarchical manner that consists of nodes connected through edges.

Tree Data Structure

It is the best alternative for the linear data structure like arrays, stacks, queues, etc as these linear data structures have high time and space complexity.

The data stored in nodes of the tree are easier to access thus reducing the time complexity.

Terms related to tree data structure

1. Node

Node of a tree

A node is an entity that stores a data element and links to its child and parent nodes.

2. Edge 

Edge of a tree

The link between any two nodes is called the edge.

3. Root

Root of a tree
The root is the transparent node in a tree that is a root node doesn't have any parent node. Here no. 1 is the Root node.

4. Parent and Child Node

The node which contains sub-nodes is called the parent node. Here 1 is the parent node for 2 and 3 and 2 is the parent node for 4 and 5.

Parent and Child Node of a tree

The node which is a descendant of any node is called a child node. Here 2 and 3 are child nodes and 1 and 4 and 5 are child nodes of 2.

5. Internal node

Internal node of a tree
A node that has at least one child node is called an Internal node. Here 1 is an internal node whereas 3 is not an internal node.

6. Leaf node (external node)

Leaf node of a tree

A node that doesn't have a child node is called a leaf node. It is the bottom-most node of a tree. Leaf nodes are commonly referred to as external nodes.

7. Height of a node

Height of a node in a tree

The number of edges from the node to the deepest leaf (leaf node) is called the height of a node. Here eight are node 1 and node 2. The height of node 2 is 1.

8. Depth of a node

Depth of a node in a tree

The no. of edges from the root to that node is called the depth of the node. Here the depth of node 2 is 1. The depth of node 5 is 2.

9. Height of a tree

Height of a tree
The height of the tree is the height of the root node to the deepest leaf node. Here the height of the tree is 2.

10. Degree of node

Degree of node in a tree
The degree of a node is the total number of branches of that node. Here node 1 has 2 degrees. Node 3 has 0 degrees as no branches are there.

Application of  a Tree

1. Trees are used to quickly check whether a data element is present in the set or not.

2. Heap tree is used to perform heap sort of elements.

3. A modified version of a tree, called tries, is utilized in modern routers for storing routing information.

4. Compilers use a syntax tree to validate the syntax of every program.

Popular Posts

Conducting Polymers: Definition, Examples, Properties and Applications

Crime Scene: Definition, Types and Characteristics

Raman Spectroscopy: Principle, Instrumentation and Applications