**Important points to be remembered about Trees: A Non-Linear Data Structure**A Tree is recursively defined as a set of one or more nodes where one node is designated as the root of the tree and all remaining nodes can be partitioned into non-empty sets each of which is a sub-tree of the root. In Figure 1.show a Tree where node 2 on the top is the root node; 7, 5 are the children of the root node 2. In the Tree below, 2, 5, 11 and 4 are the leaf nodes.

**Figure 1: Tree structure**- The tree is a widely used abstract data type and Non-Linear Data structure.
- In a Tree, the very first node is called Root Node. In above Figure, 2 is a root node
- In a Tree, the root node is the origin of tree data structure.
- Every Tree data structure must have root node like 2 in the figure above.
- The connecting link between two nodes is known as an edge.
- If Tree has 'n' number of nodes then there will be a maximum of 'n-1' edges. i.e in above figure we have 9 nodes and (9-1 = 8) edges.
- The node which is predecessor of any node is called as Parent Node i.e 6 is the parent node of 5 and 11, 9 is the parent node of 4, 5 is parent node of 9 etc
- Parent Node must have child nodes.
- A node which is descendant of any node is called as Child Node i.e 4 is the child node of 9 etc
- In Tree, all nodes except root node are child nodes. i.e 2 at the top position is never a child node.
- Nodes which belong to the same Parent and have on the same level then they are called Siblings. i.e 2, 6 are siblings, 5, 11 are siblings, 7, 5 are siblings
- In simple words, the nodes with the same parent are called as Sibling nodes.
- Any Node which does not have a child is called as Leaf Node i.e 2, 5, 11 and 4 are leaf nodes.
- Every child node will form a sub-tree of its parent node.
- A tree can be empty with no nodes or a tree
- Each node can have an arbitrary number of children may be 0, 1 and 2.
- Nodes with no children are called leaves, or external nodes.
- The depth of a node is the number of edges from the root to the node.
- A general tree is a tree where each node may have zero or more children.
- Every node in the tree is assigned a level number in such a way that the root node is at level 0, children of the root node are at level number 1.
- Degree of a node is equal to the number of children that a node has.
- The Degree of a leaf node is equal to 0.
- In-Degree of a node is the number of edges arriving at that node.
- Out-Degree of a node is the number of edges leaving that node.
- Height of the Tree is the total numbers of nodes on the path from the root node to the deepest node of the tree.
- A Tree with only a root node has a height of 1.
- The depth of the root node is 0.

**Different Types of Tree: There are different types of Tree we have in Data Structure according to there properties and features**- General Tree
- Forests Binary Trees
- Binary Search Trees
- Expression Trees
- Tournament Trees

*Thanks*

Mukesh RajputMukesh Rajput

## No comments:

## Post a Comment

Thanks

Mukesh Rajput