Lecture 274:- Strict vs Complete Binary Tree

Strict Binary Tree and Complete Binary Tree are two different types of binary trees with distinct characteristics:

1. Strict Binary Tree (Full Binary Tree):
   • In a strict binary tree, every node has exactly two children or no children at all.
   • This means that every internal (non-leaf) node in a strict binary tree must have two children.
   • There are no nodes with only one child in a strict binary tree.
   • Strict binary trees are also known as full binary trees or 2-trees.
2. Complete Binary Tree:
   • In a complete binary tree, all levels of the tree are filled except possibly the last level, and the last level is filled from left to right.
   • All levels except the last level must be completely filled, and any gaps in the last level will only occur at the rightmost positions.
   • Complete binary trees are not necessarily strict binary trees, as some nodes at the last level may have only one child.

Here's an example to illustrate the difference:

vbnetCopy code

Strict Binary Tree:        1       / \      2   3     / \    4   5 Complete Binary Tree:        1       / \      2   3     / \   \    4   5   6

In the strict binary tree, every internal node (1, 2, and 3) has exactly two children, and there are no nodes with only one child. In the complete binary tree, all levels except the last level are filled, and nodes are filled from left to right on the last level.

The key distinction between the two types is that a strict binary tree enforces the condition that every internal node must have exactly two children, while a complete binary tree focuses on filling levels from left to right, allowing for nodes with only one child at the last level.

Both types of binary trees have their unique applications and characteristics, and the choice of using one over the other depends on the specific requirements of the problem being solved.