What is a Binary Tree?

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 filled except possibly the last one
• Nodes at the last level are as far left as possible
• The maximum 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$

...