**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: