(definition)

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

**Generalization** (I am a kind of ...)

*full binary tree*, *complete binary tree*.

**See also**
*perfect k-ary tree*.

*Note:
A perfect binary tree has 2 ^{n+1}-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. After LK. *

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).*

example and formal definition.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 22 January 2008.

HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:

Yuming Zou and Paul E. Black, "perfect binary tree", in
*Dictionary of Algorithms and Data
Structures* [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 22 January 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/perfectBinaryTree.html