Tuts Master 😉

Binary Trees and It’s Different Types

Binary Trees

A binary tree is a finite set of elements that is either empty or is partitioned into three disjoint subsets. The first subset contains a single element called the root of the tree.

The other two subsets are themselves binary trees, called the left and right subtrees of the original tree. Left or right subtree can be empty. Each element of a binary tree is called a node of the tree.

In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the left child and the right child[1].

According to the above figure, all the elements 8, 4, 12,2, 5, 9, 14 etc are called as a node and here 8 is the root node. Which is simply known as the parent of 4 and 12 and grandparent of 2, 5 and 9, 14. The 4 is the left sub-tree and 12 is the right subtree.

Types of Binary Trees

  1. Strictly Binary Tree
  2. Complete Binary Tree
  3. Almost Complete Binary Tree

Strictly Binary Tree

If every nonleaf node in a binary tree has nonempty left and right sub-trees, the tree is termed as a strictly binary tree. 

If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. Or, to put it another way, all of the nodes in a strictly binary tree are of degree zero or two, never degree one.[2]

Complete Binary Tree

A complete binary tree of depth d is the strictly binary tree all of whose leaves are at level d. In a complete binary tree, there is exactly one node at level 0, two nodes at level 1, four nodes at level 2 and so on.   

Almost Complete Binary Tree

A binary tree of depth d is an almost complete binary tree, if 

  1. Any node nd at a level less than d-1 has two sons. 
  2. For any node nd in the tree with a right descendant at level d, and must have a left son and every left descendant of nd is either a leaf at level dd or has two sons. 
  3. The nodes of an almost complete binary tree are numbered in a way that the root is assigned the number 1, a left son is assigned twice the number assigned to its father, and a right son is assigned one more than twice the number assigned to its father. 

In