What is the difference between a complete binary tree and a full binary tree?

What is the difference between a complete binary tree and a full binary tree?

The main difference between a complete binary tree and a full binary tree lies in their structural properties.

A complete binary tree is a binary tree in which all levels, except possibly the last one, are completely filled, and all nodes are as left as possible. In other words, all nodes at each level are filled from left to right, and the last level may not be completely filled, but the nodes are filled from left to right. This means that there are no gaps in the tree, and it is filled in a level-by-level manner.

On the other hand, a full binary tree is a binary tree in which every node has either 0 or 2 children. In other words, every node in a full binary tree either has no children (leaf node) or has exactly two children. There are no nodes with only one child in a full binary tree.

To summarize:
- A complete binary tree focuses on the level-by-level filling of nodes, ensuring that all levels, except possibly the last one, are completely filled.
- A full binary tree focuses on the number of children each node has, ensuring that every node has either 0 or 2 children.

It is important to note that a complete binary tree can also be a full binary tree, but a full binary tree is not necessarily a complete binary tree.