Trees

In our last episode, we learned about Maps data structure. In this episode, we are going to learn about the below things on the Tree Data Structure

1) What is Tree Data Structure?

2) Architecture and Characteristics?

3) Operation Types?

4) Types of Trees?

5) Run Time Complexity Summary?

6) Examples of Real Word Scenarios where Trees are used?

So, let's get started.

1) What is Tree Data Structure?

A tree is a non-linear data structure that stores data in elements called nodes, and these nodes are connected with links called edges.

2) Architecture and Characteristics?

Well, there are many types of trees based on the order of nodes, but in this article, we will talk about the generic tree terminology, architecture, and characteristics of trees by taking a binary search tree (Its a type of Tree which we learn later) as an example.

Firstly, the tree should be completely connected, which means if you're starting from the root, there should be some way to reach every node.

A) The first or top node is called the Root Node.

B) The lines that connect all these nodes are called Edges or links, and the group of edges or links taken together is called a path.

C) Any node that has children is called a Parent Node or Internal Node.

D) Any node that doesn't have children is called Leaf Node or External Node.

E) A node can have only one parent; nodes with the same parent are called siblings.

F) The node's Height is the number of edges between it and the furthest leaf of the tree. The Height of the leaf is zero, and the Height of the parent of the leaf is one, the Height of the tree overall is the Height of the root node. The depth of the node is the number of edges between it and the root. Depth and Height are inversely proportional to each other.

G) The tree hierarchy can be expressed in Levels; the root node is at Level 0.

H) The child to the root node is at Level 1.

I) The leaf node is at Level 2, and so on and so forth.

• There shouldn't be any disconnected nodes.
• There shouldn't be any cycles in the tree; a cycle occurs when there is a way for you to encounter the same node twice.

• Finally, the root node is also called the Ancestor, and the leaf node is called the descendant.
• If a parent/internal node has children and grandchildren, then that part of the tree is known as the left or right sub-tree.

3) Operation Types?

3.1) Traversal Operations: - There are two different broad approaches called Breadth-first Search and Depth First Search, also known as BFS and DFS, respectively.

• Bread First Search: In BFS, the priority is visiting every node on the same level we're currently on before visiting child nodes; by convention, we traverse from left to right and top to bottom. BFS is also known as level order traversal.

• Depth First Search: In DFS, the priority is visiting children nodes first, by convention, we traverse from left to right.

Based on How you traverse the tree? DFS can be classified into 3 types, i.e., Pre-order, In-order, and post-order; let's have a quick look at them below.

A) Pre-order

B) In-order

C) Post-order,

3.2) Insert, Update, Delete

4) Types of Trees?

Based on the order of nodes, Trees can be divided into many types, but in this article, we will throw light on the most discussed Tree types in the computer science fraternity.

• Binary Search Tree (The one which we used in our article)
• AVL Tree
• Cartesian Tree
• B-Tree
• Red, Black Tree
• Splay Tree etc.

5) Run Time Complexity Summary?

6) Examples of Real Word Scenarios where are Trees?

• B-Tree is used in Database indexing
• Domain Name Server (DNS)
• HTML DOM etc.

I would like to conclude episode eight of our Season 2 here; stay tuned for episode 9.

References

1. Data Structures and Algorithms Made Easy in Java - Narasimha Karumanchi
2. https://www.bigocheatsheet.com/
3. https://www.udacity.com/course/data-structures-and-algorithms-in-python--ud513
4. https://www.geeksforgeeks.org/real-time-application-of-data-structures/
5. https://www.diagrams.net/

Disclaimer

This article is governed by the "Fair Use" doctrine and is only for purposes such as criticism, comment & teaching.

Note: - This is a live article.