# Important points to be remembered about Trees: A Non-Linear Data Structure

Tree Data Structure, Non-Linear Data Structure
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 Rajput

Mukesh Rajput

I am a Computer Engineer, a small amount of the programming tips as it’s my hobby, I love to travel and meet people so little about travel, a fashion lover and love to eat food, I am investing a good time to keep the body fit so little about fitness also..