# Binary Tree

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

## 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]

1. Rowan Garnier; John Taylor (2009). Discrete Mathematics: Proofs, Structures and Applications, Third Edition. CRC Press. p. 620. ISBN 978-1-4398-1280-8.
2. Steven S Skiena (2009). The Algorithm Design Manual. Springer Science & Business Media. p. 77. ISBN 978-1-84800-070-4.
3. Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. p. 363. ISBN 0-201-89683-4.
4. Iván Flores (1971). Computer programming system/360. Prentice-Hall. p. 39.
5. David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. p. 246. ISBN 978-0-88385-762-5.
6. David Makinson (2009). Sets, Logic and Maths for Computing. Springer Science & Business Media. p. 199. ISBN 978-1-84628-845-6.
7. Jonathan L. Gross (2007). Combinatorial Methods with Computer Applications. CRC Press. p. 248. ISBN 978-1-58488-743-0.
8. 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.
9. L.R. Foulds (1992). Graph Theory Applications. Springer Science & Business Media. p. 32. ISBN 978-0-387-97599-3.