NIST

full binary tree

(data structure)

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

Also known as proper binary tree.

Generalization (I am a kind of ...)
binary tree.

Specialization (... is a kind of me.)
coding tree, perfect binary tree.

Aggregate parent (I am a part of or used in ...)
Huffman coding.

See also complete binary tree.

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

After Mustafa Ege (ege@eti.cc.hun.edu.tr) Hacettepe University, comp.theory, 17 November 1998. Also [CLR90, page 95], and [Stand98, page 248].

This kind of tree is called "proper" by Goodrich & Tamassia page 231.

Sahni, page 461, and Carrano & Prichard, page 429, define full binary tree the way we define a perfect binary tree.

Author: PEB


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

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

Entry modified 27 August 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "full binary tree", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 27 August 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/fullBinaryTree.html