Skip to main content

Tree Data Structure and Its all types

 

What are tree Data Structures?

  • Tree is a hierarchical data structure that stores the information naturally in the form of a hierarchy style.
  • Tree is one of the most powerful and advanced data structures.
  • It is a non-linear data structure compared to arrays, linked lists, stack, and queue.
  • It represents the nodes connected by edges.
structure of tree

The above figure represents the structure of a tree. Tree has 2 subtrees.
A is a parent of B and C.
B is called a child of A and also a parent of D, E, F.

Tree is a collection of elements called nodes, where each node can have an arbitrary number of children.

FieldDescription
RootRoot is a special node in a tree. The entire tree is referenced through it. It does not have a parent.
Parent NodeParent node is an immediate predecessor of a node.
Child NodeAll immediate successors of a node are its children.
SiblingsNodes with the same parent are called Siblings.
PathPath is a number of successive edges from source node to destination node.
Height of NodeHeight of a node represents the number of edges on the longest path between that node and a leaf.
Height of TreeHeight of tree represents the height of its root node.
Depth of NodeDepth of a node represents the number of edges from the tree's root node to the node.
Degree of NodeDegree of a node represents a number of children of a node.
EdgeEdge is a connection between one node to another. It is a line between two nodes or a node and a leaf.

In the above figure, D, F, H, G are leaves. B and C are siblings. Each node excluding a root is connected by a direct edge from exactly one other node
parent →  children.

Levels of a node

Levels of a node represent the number of connections between the node and the root. It represents a generation of a node. If the root node is at level 0, its next node is at level 1, its grandchild is at level 2, and so on. Levels of a node can be shown as follows:

levels of tree

Note:

- If node has no children, it is called Leaves or External Nodes.

- Nodes which are not leaves, are called Internal Nodes. Internal nodes have at least one child.

- A tree can be empty with no nodes or a tree consists of one node called the Root.

Height of a Node

height of node

As we studied, height of a node is a number of edges on the longest path between that node and a leaf. Each node has height.

In the above figure, A, B, C, D can have height. Leaf cannot have height as there will be no path starting from a leaf. Node A's height is the number of edges of the path to K not to D. And its height is 3.

Note:

- Height of a node defines the longest path from the node to a leaf.

- Path can only be downward.

Depth of a Node

depth of node

While talking about the height, it locates a node at bottom where for depth, it is located at top which is root level and therefore we call it depth of a node.

In the above figure, Node G's depth is 2. In depth of a node, we just count how many edges between the targeting node & the root and ignoring the directions.

Note: Depth of the root is 0.

Advantages of Tree

  • Tree reflects structural relationships in the data.
  • It is used to represent hierarchies.
  • It provides an efficient insertion and searching operations.
  • Trees are flexible. It allows to move subtrees around with minimum effort.

Comments

Popular posts from this blog

Complete Tutorial on Business Analytics

CRISP-DM (Cross Industry Standard Process for Data Mining)                                    The framework is made up of 6 steps: Business Issue Understanding Data Understanding Data Preparation Analysis/Modeling Validation Presentation/Visualization The map outlines two main scenarios for a business problem: Data analysis Predictive analysis Data analysis refers to the more standard approaches of blending together data and reporting on trends and statistics and helps answer business questions that involve understanding more about the dataset such as "On average, how many people order coffee and a donut per transaction in my store in any given week?" Predictive analysis will help businesses predict future behavior based on existing data such as "Given the average coffee order, how much coffee can I expect to sell next week if I were to add a new brand of coffee?" Business Issue Understanding "This initial phase focuses on understanding the project objectives a

What is a Type II Error?

  A Type II error is a false negative in a test outcome, where something is falsely inferred to not exist. This usually means incorrectly accepting the null hypothesis (H0), which is the testing statement that whatever is being studied has no statistically significant effect on the problem. An example would be a drug trial that incorrectly concludes the prescribed medication had no effect on the patient’s ailment, when in fact the disease was cured, but subsequent exams caused a false positive showing the patient was still sick. Null Hypothesis and Statistical Significance In practice, the difference between a false positive and a false negative is usually not so clear-cut. Since the tests are most often quantitively rather than qualitatively based, the results tend to be expressed in a confidence interval value less than 100%, rather than a simple Yes/No decision. This question of how likely the results are to be found if the null hypothesis is true is called statistical significance.

What is Difference between Data Science, Machine Learning, Deep Learning, AI and StatisticsI

In this article, I will be telling you about the different roles of data scientist and how data science compares and overlaps with related fields such as Machine Learning, Deep Learning, AI, Applied Mathematics, Linear Algebra and Statistics. Data Science is a broad discipline, I start by describing the different types of data scientists that one may encounter in any business setting. You might discover that you are a data scientist yourself, without knowing it. As with any scientific discipline, Data science may borrow techniques from related disciplines. Pictures are the best way to represent anything, from below given pictorial representation you can understand that what is the overlapping of Different fields with Data science. 1- Different Types  of Data Scientist Here in this section, I will be talking about types of Data Scientist ♦ The Type A Data Scientist can code well enough to work with data but is not necessarily an expert. The Type A data scientist may be an ex