What's the difference between a full and a complete binary tree?

A full binary tree has all nodes with either 0 or 2 children, while a complete binary tree is fully filled except the last level.

A full binary tree, also known as a proper or plane binary tree, is a tree in which every node has either 0 or 2 children. In other words, a node can either be a leaf node with no children or an internal node with two children. This means that there are no nodes with only one child in a full binary tree. The number of leaf nodes in a full binary tree is always one more than the number of internal nodes.

On the other hand, a complete binary tree is a binary tree in which all levels, except possibly the last, are completely filled, and all nodes are as far left as possible. This means that a complete binary tree can have nodes with only one child, but these nodes are always to the left of nodes with two children. The last level of a complete binary tree is filled from left to right.

In terms of their applications, full binary trees are often used in mathematical expressions and boolean functions as they provide a clear and straightforward structure. Complete binary trees, however, are used in many data structures like binary heaps, which are used in heap sort, a common sorting algorithm.

In summary, while both full and complete binary trees are types of binary trees, they have different structures and uses. A full binary tree has all nodes with either 0 or 2 children, and the number of leaf nodes is always one more than the number of internal nodes. A complete binary tree, however, is fully filled except the last level, and all nodes are as far left as possible.