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.