Basic Tree Concepts and Definitions
Tree
A Tree is defined as a finite set of one or more nodes such that:
• There is a special node called root node having no predecessor.
• All the nodes in a tree except root node having only one predecessor.
• All the nodes in a tree having 0 or more successors.
Consider Following Figure:
Forest
A forest is a collection of two or more disjoint tree.
Consider Following Figure in which a forest is a collection of two disjoint tree.
In Degree
In a tree number of edges comes in to particular node is called Indegree of that particular node. Root node having indegree always equals to 0 because it is the first node of tree.
In above figure indegree of each node is given below:
Node |
Indegree |
A |
0 |
B |
1 |
C |
1 |
D |
1 |
E |
1 |
F |
1 |
G |
1 |
Out Degree
In a tree number of edges comes out from particular node is called Out degree of that particular node. Leaf node having out degree always equals to 0 because it is the last node of tree having no further sub tree.
In above figure out degree of each node is given below:
Node |
Out degree |
A |
2 |
B |
2 |
C |
2 |
D |
0 |
E |
0 |
F |
0 |
G |
0 |
Degree or Total Degree
In a tree the sum of edges comes into particular node and edges comes out from particular node is called degree of that particular node. It means Degree is the sum of in degree and out degree. It is also called total degree of node.
In above figure degree of each node is given below:
Node |
Degree |
A |
2 |
B |
3 |
C |
3 |
D |
1 |
E |
1 |
F |
1 |
G |
1 |
Root Node
A node having in degree equal to 0 is called Root Node.
It is the first node of tree.
Leaf Node
A node having out degree equals to 0 is called Leaf Node.
Leaf Node does not have any sub tree.
Path
A sequence of connecting edges from one node to another node is called Path.
Consider Following Figure:
In above figure path from Node A to H is given as A->B->D->H
In above figure path from Node A to I is given as A->C->G->I
Depth
The length of the path from Root Node to particular Node V is called depth of node V.
In above figure depth of node E is 2 because the Path from Root Node A to Node E is A->B->E. Here the length of the Path is 2 so depth of node E is 2.
Depth of Node H is 3 because the path from Root Node A to Node H is A->B->D->H. Here the Length of the Path is 3 so depth of node H is 3.
Depth of the tree can be defined as the length of the path from Root Node to the deepest node in the tree.
Binary Tree
A Tree in which out degree of each node is less then or equal to 2 but not less then 0 is called binary tree.
We can also say that a tree in which each node having either 0, 1 or 2 child is called binary tree.
In above figure node A having 2 child, node B having 1 child, node C having 2 child, node D, F and G having 0 child. So we can say that it is binary tree.
Complete Binary Tree
A Tree in which out degree of each node is exactly equals to 0 or 2 is called Complete Binary Tree.
We can also say that a tree in which each node having either 0 or 2 child is called Complete Binary Tree.
In above figure node A having 2 child, node B having 0 child, node C having 2 child, node F and G having 0 child. So we can say that it is Complete Binary Tree.
Similar Binary Tree
If two binary trees are similar in structure then they are said to be similar binary trees.
Consider following figure:
Copies of Binary Tree
If two binary trees are similar in structure and their corresponding nodes having same value then they are said to be copies of binary trees.
Consider following figure:
