Introduction

The only characteristic which separates Binary Tree from N-ary trees is that any internal-node (non-leaf node) can only contain a maximum of two child nodes. Each node strictly has reference to a left and a right node; we call them its left and right child. The figure below shows what a Binary Tree looks like:

Types of Binary Trees

The following are further variations of binary trees, based on the structure and other features:

• Complete Binary Tree
• Full Binary Tree
• Perfect Binary Tree

Starting with Complete Binary Tree, let’s discuss each one of them and look at their characteristics and structure.

Complete Binary Tree

A Binary Tree is said to be complete if it satisfies the following properties:

• All levels are filed except possibly the last one
• Nodes at the last level are as far left as possible
• The total number of nodes in a complete binary tree of height “h” are expressed as  $2^{h + 1} - 1$
• The total number of non-leaf nodes in a complete binary tree of height “h” are expressed as $2^{h - 1}$
• The total number of leaf nodes in a complete binary tree of height “h” is expressed as ​​$2^{h}$
• The nodes are present in between the range of:

Full Binary Tree