5

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, enter image description here

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,

enter image description here

as Full Binary Tree.

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

lu5er
  • 3,229
  • 2
  • 29
  • 50
  • Possible duplicate of [Difference between "Complete binary tree", "strict binary tree","full binary Tree"?](https://stackoverflow.com/questions/12359660/difference-between-complete-binary-tree-strict-binary-tree-full-binary-tre) – Ted Hopp Aug 02 '17 at 00:17
  • @TedHopp, if you go to http://gateoverflow.in/122126/full-binary-tree-complete-almost-complete-binary-difference and see the `Fig 1`, that is what they claim to be FULL binary tree. My question is different I guess. – lu5er Aug 02 '17 at 00:23
  • What your professor calls a "full binary tree", I would call a "balanced binary tree". – Gordon Linoff Aug 02 '17 at 00:24
  • @GordonLinoff, But for a balanced tree is it necessary that all leaves must be in the same level? https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree#/media/File:AVLtreef.svg – lu5er Aug 02 '17 at 00:32
  • @IU5er . . . Not at the same level, but at the same level or level - 1. Balanced trees are how most database indexes are implemented, and the consistent height is important for performance. – Gordon Linoff Aug 02 '17 at 01:46
  • @GordonLinoff, I get what you are saying. I just wanted to say that the first definition does not imply that it's a balanced tree but rather a perfect tree as the answers point out. – lu5er Aug 02 '17 at 02:04
  • I've got a professor (in addition to [this textbook](http://www.cs.williams.edu/JavaStructures/Welcome.html)) that uses the term "full" to refer to "perfect" binary trees as well. – Guy Dec 01 '18 at 01:28

2 Answers2

5

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.

A. Mashreghi
  • 1,729
  • 2
  • 20
  • 33
4

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.

Ted Hopp
  • 232,168
  • 48
  • 399
  • 521