What is a Binary Tree?
Understand the fundamental concept of binary trees, including their unique two-child node structure. Explore key types such as complete, full, and perfect binary trees by learning their defining properties, node counts, and structural differences.
We'll cover the following...
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
- The total number of non-leaf nodes in a complete binary tree of height “h” are expressed as