Definition of Full Binary Tree

Question

I came upon two resources and they appear to say the basic definition in two ways.

Source 1 (and one of my professor) says:

All leaves are at the same level and all non-leaf nodes have two child nodes.

Source 2 (and 95% of internet) says:

A full binary tree (sometimes referred to as a proper or plane binary tree) is a tree in which every node in the tree has either 0 or 2 children.

Now following Source 2,

becomes a binary tree but not according to Source 1 as the leaves are not in the same level.

So typically they consider trees like,

as Full Binary Tree.

I may sound stupid but I'm confused what to believe. Any help is appreciated. Thanks in advance.

Answer 1

There are three main concepts: (1) Full binary tree (2) Complete binary tree and (3) Perfect binary tree. As you said, full binary tree is a tree in which all nodes have either degree 2 or 0. However, a complete binary tree is one in which all levels except possibly the last level are filled from left to right. Finally, a perfect binary tree is a full binary tree in which all leaves are at the same depth. For more see the wikipedia page

My intuition for the term complete here is that given a fixed number of nodes, a complete binary tree is made by completing each level from left to right except possibly the last one, as the number of nodes may not always be of the form 2^n - 1.

Answer 2

I think the issue is, what's the purpose of making the definition? Usually, the reason for defining full binary tree in the way that appears in Wikipedia is to be able to introduce and prove the Full Binary Tree Theorem:

The total number of nodes N in a full binary tree with I internal nodes is 2 I + 1.

(There are several equivalent formulations of this theorem in terms of the number of interior nodes, number of leaf nodes, and total number of nodes.) The proof of this theorem does not require that all the leaf nodes be at the same level.

What one of your professors is describing is something I would call a perfect binary tree, or, equivalently, a full, complete binary tree.