The basics of Binary Trees

A tree is called a binary tree if each node has zero child, one child or two children. Empty tree is also a valid binary tree. We can visualize a binary tree as consisting of a root and two disjoint binary trees, called the left and right sub-trees of the root.

Generic Binary Tree

Types of Binary Trees

Strict Binary Tree:

A tree is called a strict binary tree if each node has exactly two children or no children.

Full Binary Tree:

A binary tree is called a full binary tree if each node has exactly two children and all leaf nodes are at the same level.

Complete Binary Tree:

Before defining the complete binary tree, let us assume that the height of the binary tree is h. In complete binary trees, if we give numbering for the nodes by starting at root (let us say the root node has 1) then we get a complete sequence from 1 to number of nodes in the tree.While traversing we should give numbering for NULL pointers also. A binary tree is called a complete binary tree if all leaf nodes are at height h or h-1 and also without any missing number in the sequence.

Properties of Binary Trees

For the following properties, let us assume that the height of the tree is h. Also, assume that root node is at height zero. From the diagram shown below we can infer the following properties.

• The number of nodes ‘n’ in a full binary tree is 2^h+1 – 1. Since, there are h levels we need to add all nodes at each level [2⁰ + 2¹ + 2² + ….. + 2^h = 2^h+1 – 1]
• The number if nodes n in a complete binary tree is between 2^h (minimum) and 2^h+1 – 1 (maximum).
• The number of leaf nodes in a full binary tree are 2^h.
• The number of NULL links (wasted pointers) in a complete binary tree of n nodes are n+1.