Data Structure

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. 


About Author provides tutorials related to tech and programmings. We are also setting up a community for the users and students.

You may also like

data types
Data Structure Differences

Difference Between Primitive and Non-Primitive Data Types

  • July 22, 2019
Primitive data type: In simple terms “data type” and “primitive data type” are simply known and used as interchangeable variables. Primitive
data structure
Data Structure What is & Queries

What is Data Structure? Why Do We Require This?

  • July 28, 2019
Question: What is Data Structure? Data is the basic factor entity that is utilized in calculation or manipulation. There are two different type