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

Image
What are Conducting Polymers? As the name suggests organic polymers that conduct electricity are known as conducting polymers. They are also known as intrinsically conducting polymers (ICPs) and they have alternating single and double bonds along the polymer backbone (conjugated bonds) or that are composed of aromatic rings such as Phenylene, naphthalene, anthracene, pyrrole, and thiophene which are connected through carbon-carbon single bonds. Examples: Polyacetylene, Polypyrrole, Polyaniline, etc What is the reason behind conducting nature of these polymers? Conducting polymers comes in two forms that are doped conducting polymers and non-doped conducting polymers. The conductivity of non-doped conjugated polymers is due to the existence of a conductivity band similar to a metal. In a conjugated polymer, three of the four valence electrons form strong sigma bonds through sp² hybridization where electrons are strongly localized. The remaining unpaired electron of each carbon atom re
Read more

Crime Scene: Definition, Types and Characteristics

Image
What is a Crime Scene ? A place where the crime is committed or where the maximum physical evidence related to crime is found is known as a crime scene. A crime scene is a starting point of the investigation which provides information about the suspect and the victim. This helps to reconstruct the crime and fast resolution of the case. It is noted that the crime scene is not limited to a single place but may extend to a wider area depending upon the nature of the crime committed. For example, In a murder case where murder is done at one place and the body is disposed on another place. In this case, we have two crime scenes that give information about the crime. Types of Crime Scene Based on evidence found on the crime scene: 1. Primary Crime Scene The crime scene where the actual crime occurred or where more usable pieces of evidence were found is known as the primary crime scene. For example, A murder scene, theft, assault, etc. 2. Secondary Crime Scene The crime scene which is some
Read more

Documentation of the Crime Scene: Step by Step

Image
What is documentation of the crime scene and Why it is done? After securing the crime scene, the next most important step is documentation of the crime scene because documentation permanently records the crime scene and its physical evidence. Documentation should be done without any wastage of time as the scene and its evidence may get altered over time. The documentation should be done innovatively and the originality of the crime scene should be maintained and documentation should not have pauses or breaks, it should remain constant till the whole crime scene is documented. There are four main tasks of documentation that is note-making, photography, videography , and sketching . It should be noted that all four tasks are necessary and none is a substitute for another. For example, notes are not substitutes for photography, video is not a substitute for sketching, etc. Following are the sequence for crime scene documentation: 1. Note making Documentation of crime scene in the f
Read more