Binary Tree, Full Binary Tree, Complete Binary Tree

---

Binary Tree

---

Definition: A tree with at most two children for each node.

Formal Definition: A binary tree either 

• is empty (no nodes), or
• has a root node, a left binary tree, and a right binary tree.

It's also known as dyadic tree.

---

Full Binary Tree

---

Definition: A binary tree in which each node has exactly zero or two children.

Also known as proper binary tree.

In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding is a full binary tree.

---

Complete Binary Tree

---

Definition: A binary tree in which every level (depth), except possibly the deepest, is completely filled. At depth n, the height of the tree, all nodes must be as far left as possible.

A complete binary tree has 2^k nodes at every depth k < n and between 2ⁿ and 2ⁿ⁺¹-1 nodes altogether. It can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2, with 1-based indexing. If the child index is greater than the number of nodes, the child does not exist.

---

Perfect Binary Tree

---

A binary tree with all leaf nodes at the same depth. All internal nodes have degree 2.

A perfect binary tree has 2ⁿ⁺¹-1 nodes, where n is the height. It can be efficiently implemented as an array, where a node at index i has children at indexes 2i and 2i+1 and a parent at index i/2.

A complete binary tree may be seen as a perfect binary tree with some extra leaf nodes at depth n+1, all toward the left. (After [CLR90, page 140]).

This kind of tree is called "complete" by some authors ([CLR90, page 95], Leighton) and "full" by others (Budd page 331, Carrano & Prichard page 429, Ege, [HS83, page 225], and Sahni page 461).

Happy Exploring!