(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 2n+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).
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 27 November 2019.
HTML page formatted Wed Nov 27 08:41:29 2019.
Cite this as:
Yuming Zou and Paul E. Black, "perfect binary tree", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 27 November 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/perfectBinaryTree.html