Editing Binary tree (section)

{{Short description|Limited form of tree data structure}}
{{Distinguish|Binary search tree|B-tree|B+ tree}}
[[File:Binary tree v2.svg|thumb|alt=A labeled binary tree of size 9 and height 3, with a root node whose value is 1. The above tree is unbalanced and not sorted.|A labeled binary tree of size 9 (the number of nodes in the tree) and height 3 (the height of a tree defined as the number of edges or links from the top-most or root node to the farthest leaf node), with a root node whose value is 1. The above tree is unbalanced and not sorted.]]

In [[computer science]], a '''binary tree''' is a [[Tree (data structure)|tree data structure]] in which each node has at most two [[child node|children]], referred to as the ''left child'' and the ''right child''. That is, it is a [[m-ary tree|''k''-ary tree]] with {{math|''k'' {{=}} 2}}. A [[recursive definition]] using [[set theory]] is that a binary tree is a [[Triple (mathematics)|triple]] {{nowrap|(''L'', ''S'', ''R'')}}, where ''L'' and ''R'' are binary trees or the [[empty set]] and ''S'' is a [[Singleton (mathematics)|singleton]] (a single–element set) containing the root.<ref name="GarnierTaylor2009">{{cite book| author1=Rowan Garnier| author2=John Taylor| title=Discrete Mathematics:Proofs, Structures and Applications, Third Edition|url=https://books.google.com/books?id=WnkZSSc4IkoC&pg=PA620|year=2009|publisher=CRC Press|isbn=978-1-4398-1280-8|page=620}}</ref><ref name="Skiena2009">{{cite book|author=Steven S Skiena|title=The Algorithm Design Manual| url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA77|year=2009| publisher=Springer Science & Business Media| isbn=978-1-84800-070-4|page=77}}</ref>

From a [[graph theory]] perspective, binary trees as defined here are [[Arborescence (graph theory)|arborescences]].<ref name="Knuth1997">{{cite book| author=Knuth |title=The Art Of Computer Programming, Volume 1, 3/E| year=1997| publisher=Pearson Education| isbn=0-201-89683-4|page=363}}</ref> A binary tree may thus be also called a '''bifurcating arborescence''',<ref name="Knuth1997"/> a term which appears in some early programming books<ref name="Flores1971">{{cite book| author=Iván Flores|title=Computer programming system/360|year=1971| publisher=Prentice-Hall| page=39}}</ref> before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an [[undirected graph|undirected]], rather than [[directed graph]], in which case a binary tree is an [[ordered tree|ordered]], [[rooted tree]].<ref>{{cite book| author=Kenneth Rosen|title=Discrete Mathematics and Its Applications, 7th edition|year=2011|publisher=McGraw-Hill Science|page=749|isbn=978-0-07-338309-5}}</ref> 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.<ref name="Mazur2010">{{cite book|author=David R. Mazur |title=Combinatorics: A Guided Tour| url=https://books.google.com/books?id=yI4Jx5Obr08C&pg=PA246|year=2010|publisher=Mathematical Association of America |isbn=978-0-88385-762-5|page=246}}</ref>

In mathematics, what is termed ''binary tree'' can vary significantly from author to author. Some use the definition commonly used in computer science,<ref name="oem"/> but others define it as every non-leaf having exactly two children and don't necessarily label the children as left and right either.<ref name="Foulds1992">{{cite book|author=L.R. Foulds|title=Graph Theory Applications |url=https://books.google.com/books?id=IK7kreGl3vkC&pg=PA32| year=1992| publisher=Springer Science & Business Media|isbn=978-0-387-97599-3|page=32}}</ref>

In computing, binary trees can be used in two very different ways:

*First, as a means of accessing nodes based on some value or label associated with each node.<ref name="Makinson2009b">{{cite book|author=David Makinson| title=Sets, Logic and Maths for Computing|year=2009|publisher=Springer Science & Business Media| isbn=978-1-84628-845-6|page=199}}</ref> Binary trees labelled this way are used to implement [[binary search tree]]s and [[binary heap]]s, and are used for efficient [[search algorithm|searching]] and [[Sorting algorithm|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.<ref name="Gross2007">{{cite book|author=Jonathan L. Gross| title=Combinatorial Methods with Computer Applications |url=https://books.google.com/books?id=hamtabmh0ZoC&pg=PA248| year=2007| publisher=CRC Press|isbn=978-1-58488-743-0|page=248}}</ref> However, the arrangement of particular nodes into the tree is not part of the conceptual information. For example, in a normal binary search tree the placement of nodes depends almost entirely on the order in which they were added, and can be re-arranged (for example by [[Self-balancing binary search tree|balancing]]) without changing the meaning.
*Second, as a representation of data with a relevant bifurcating structure. In such cases, the particular arrangement of nodes under and/or to the left or right of other nodes is part of the information (that is, changing it would change the meaning). Common examples occur with [[Huffman coding]] and [[cladograms]]. The everyday division of documents into chapters, sections, paragraphs, and so on is an analogous example with ''n''-ary rather than binary trees.