# binary tree

(data structure)

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

**Also known as** dyadic tree.

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

*tree*, *k-ary tree* with k=2.

**Specialization** (... is a kind of me.)

*complete binary tree*, *full binary tree*, *binary search tree*, *binary heap*, *balanced binary tree*, *threaded tree*, *Merkle tree*, *Fibonacci tree*, *extended binary tree*.

*Note:
Formal definition after [CLR90, page 94].*

Author: PEB

## Implementation

examples, analysis, and code (C). Bro. David Carlson's tutorial and code (C++). Worst-case behavior of traversal, annotated for real time (WOOP/ADA).
## More information

**Historical Note**

An early use of the term "dyadic tree" is in **Georgii M. Adelson-Velskii** and **Evgenii M. Landis**, *An algorithm for the organization of information*, Doklady Akademii Nauk SSSR, 146:263-266, 1962 (Russian). English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259-1263, 1962.

(Doklady is Russian for "Report". Sometimes transliterated in English as Doclady or Dokladi.)

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 15 December 2017.

HTML page formatted Wed Mar 13 12:42:45 2019.

Cite this as:

Paul E. Black, "binary tree", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 15 December 2017. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/binarytree.html