Tree Data structure— Part-I
Fundamentals
Hi There, let me introduce myself before diving into the topic as this is my very first medium article.
“Im, Tirupati Rao (from India). I believe sharing knowledge with others is also a part of learning. I will keep adding topics on all data structures starting from fundamentals to solving related coding problems topic-wise. Hope this will help you in understanding and preparing for the coding interviews.”
“The trees are one of the most important Non-Linear data structures widely used to store and solve the problems associated with complex data”
In this article, we explore the basic associated terms with Trees, so moving further will help to understand all different kinds of Tree data structures.
Tree: A tree is a collection of nodes and edges.
- In the below diagram A, B, and C…..up to L are called Nodes and paths connecting between any two nodes are Edges.
- In a tree, if there are N number of Nodes then there will be N-1 no of Edges.
- (Root) will not have any edge pointing to it. So N-1 edges.
Common Terminologies of Tree:
Root: The root Node is the first Top node or node without any parents.
Parent: A node is called the Parent node to its next Descendant nodes.
Child: Descendant nodes of any root are called Child nodes, which are commonly connected to their precedent node(s)
Siblings: Siblings are children of the same Parent node
Ex: B, C, and D are siblings (from above diagram)
Descendents: All the reachable child nodes from a particular node are descendants of that node.
* For the root node, all other nodes are descendants.
Ex: E, F, I & J are Descendent of node B
Degree of a Node: The degree of any node is the count of immediate children to that node.
Ex: Degree of Node ‘A’ is 3
The degree of Node ‘B’ is 2
Degree of a Tree: The degree of a tree is the maximum degree of any node.
Ex: Degree of Tree is 3 (Max degree Node ‘A’ is 3)
Internal Nodes: The nodes having degrees more than zero are known as Internal/Inner nodes.
Ex: B, C, D, F, and H are internal nodes
External Nodes: The nodes having degrees of zero are known as External/Leaf nodes.
Ex: E, G, I, J, K, and L are External or Leaf nodes.
Level: The level of any Tree starts from 1 (at the Root node). The level can be calculated as no nodes visible on the left/ right side of the given tree from the root.
Ex:
The level at the Root node is — 1
The level at Node B is — 2
The level at Node H is — 3
The level at Node L is — 4
Height: Height at any node is no of edges till that node. So Height of the Root starts at zero
Height = Level — 1 at any Node.
Forest: In the common collection of Multiple trees is known as Forest.
I hope you are clear with these basic and important terminologies of Tree data structure. Let’s further dive into Different kinds of Trees.
- Binary Tree (Bi-2): A Tree is called a Binary tree, where any node Strictly will have either 0 or 1 or 2 child nodes at most.
So the degree of the Binary tree always lies between zero to Two.
Skewed Tree: This is a kind of binary tree where the degree of the tree is always 1.
In the above diagram, we have two Binary Trees. One is Left Skewed and another is Right Skewed tree.
We will continue to explore the Binary Tree data structure further in our next article. Thanks for Reading and 👏👏👏
Next:
#arraysinjava. #array #datastructures #codinginterviewquestions #codinginterview #faang #leetcode #animated #java #python #faang #motion
