# Binary Tree

# Binary Tree Introduction

A binary tree is a non-linear data structure used for data storage. It is a special type of tree because it has at most two children. One is Left Child and one is Right Child. Its like a combination of sorted array and linked list because search function in it is as fast as in sorted array and insertion and deletion is as fast as linked list.

## Terminology required to understand Binary Tree

For the Given Tree –

### Left Sub-Tree –

### Right Sub-Tree –

### Same Generation Nodes –

Nodes at same level are termed as Same Generation Nodes.

Eg – Node with data 2,6 are same generation Nodes

### Child Nodes –

All nodes except Root node are child node except root node or we can say nodes with parents are child nodes.

Eg – Nodes with data 1,2,3,5,6,7

### Leaf Nodes –

Nodes Without Childs are known as Leaf Nodes.

Eg – Nodes with data 1,3,5,7

### Sibling Nodes –

Nodes with same parent are sibling nodes.

Eg – 1&3 , 2&6 , 5&7

### Depth of Node –

In simple words the distance between node and root node is called depth of node.

### Height of Tree –

Number of generations of that node is termed as height of tree.

## Types Of Binary Tree

**Full Binary tree –**

It is also known as Proper and strict Binary Tree. In this type of tree all nodes contain either 0 or 2 children.

**Properties of Full Binary Tree**

Here we are taking –

n = Number of Nodes

h = Height of Binary Tree

m = number of leaf nodes

- Maximum Number of Nodes – 2^(h+1)- 1

- Minimum Number of Nodes – 2*h – 1

- Maximum Height of Full Binary Tree – log2(n+1) – 1

- Minimum Height of Full Binary Tree – (n+1)/2

- Total Number of nodes = 2*m -1

**Complete Binary tree – **

In this type of tree all nodes levels are files except the last level. In last level elements should be filled as left as possible.

**Properties of Full Binary Tree**

Here we are taking –

n = Number of Nodes

h = Height of Binary Tree

- Maximum Number of Nodes – 2^(h+1)- 1

- Minimum Number of Nodes – 2*h

- Maximum & Minimum Height of Full Binary Tree – log2(n+1) – 1

**Perfect Binary tree – **

In this type of tree all nodes contain 2 children.

**Degenerate Binary tree – **

In this type of tree all nodes stickily contain 1 child node.

**Balanced Binary tree – **

In this type of tree number of nodes of left sub tree and right sub tree differ by at most 1.