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.

Forest
     

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.

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.

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.

Tree

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.

Root Node and Leaf Node

Path

A sequence of connecting edges from one node to another node is called Path.
Consider Following Figure:

Path

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.

BinaryTree

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.

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:

Similar Binary Tree

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:

Copies of Binary Tree

Download Projects


Download Programs