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.

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 Carrano & Prichard page 427, [CLR90, page 95], and [Stand98, page 248].

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

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 E. Black.

Entry modified Mon Jan 24 13:56:22 2005.
HTML page formatted Wed Oct 26 09:47:33 2005.

Cite this as:
Paul E. Black, "full binary tree", from Dictionary of Algorithms and Data Structures, Paul E. Black, ed., NIST.
http://www.nist.gov/dads/HTML/fullBinaryTree.html