# Binary Tree

A Binary Tree is a tree data structure in which graph node a maximum of 2 child nodes.

**Example(s):****Counter-Example(s):****See:**Sorting Algorithm, Tree Structure, Data Structure, Child Node, Recursive Process, Set Theory, Tuple, Empty Set, Singleton Set, Graph Theory, Arborescence (Graph Theory).

## References

### 2018

- (Wikipedia, 2018) ⇒ https://en.wikipedia.org/wiki/Binary_tree Retrieved:2018-2-25.
- In computer science, a
**binary tree**is a tree data structure in which each node has at most two children, which are referred to as the '**and the '**. A recursive definition using just set theory notions is that a (non-empty) binary tree is a tuple (*L*,*S*,*R*), where*L*and*R*are binary trees or the empty set and*S*is a singleton set.^{[1]}Some authors allow the binary tree to be the empty set as well.^{[2]}From a graph theory perspective, binary (and K-ary) trees as defined here are actually arborescences.

^{[3]}A binary tree may thus be also called a**bifurcating arborescence**— a term which appears in some very old programming books,^{[4]}before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an undirected, rather than a directed graph, in which case a binary tree is an ordered, rooted tree. Some authors use**rooted binary tree**instead of*binary tree*to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted.^{[5]}A binary tree is a special case of an ordered K-ary tree, where*k*is 2. In computing, binary trees are seldom used solely for their structure. Much more typical is to define a labeling function on the nodes, which associates some value to each node.^{[6]}Binary trees labelled this way are used to implement binary search trees and binary heaps, and are used for efficient searching and sorting. The designation of non-root nodes as left or right child even when there is only one child present matters in some of these applications, in particular it is significant in binary search trees.^{[7]}In mathematics, what is termed*binary tree*can vary significantly from author to author. Some use the definition commonly used in computer science,^{[8]}but others define it as every non-leaf having exactly two children and don't necessarily order (as left/right) the children either.^{[9]}

- In computer science, a

- ↑ Rowan Garnier; John Taylor (2009). Discrete Mathematics: Proofs, Structures and Applications, Third Edition. CRC Press. p. 620. ISBN 978-1-4398-1280-8.
- ↑ Steven S Skiena (2009). The Algorithm Design Manual. Springer Science & Business Media. p. 77. ISBN 978-1-84800-070-4.
- ↑ Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. p. 363. ISBN 0-201-89683-4.
- ↑ Iván Flores (1971). Computer programming system/360. Prentice-Hall. p. 39.
- ↑ David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. p. 246. ISBN 978-0-88385-762-5.
- ↑ David Makinson (2009). Sets, Logic and Maths for Computing. Springer Science & Business Media. p. 199. ISBN 978-1-84628-845-6.
- ↑ Jonathan L. Gross (2007). Combinatorial Methods with Computer Applications. CRC Press. p. 248. ISBN 978-1-58488-743-0.
- ↑ Hazewinkel, Michiel, ed. (2001) [1994], "Binary tree", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 also in print as Michiel Hazewinkel (1997). Encyclopaedia of Mathematics. Supplement I. Springer Science & Business Media. p. 124. ISBN 978-0-7923-4709-5.
- ↑ L.R. Foulds (1992). Graph Theory Applications. Springer Science & Business Media. p. 32. ISBN 978-0-387-97599-3.