Binary tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a binary tree is a <a href="/facts/Tree_(data_structure)/RcXz9noF">tree data structure</a> in which each node has at most two <a href="/facts/Child_node/RcXz9noF">children</a>, referred to as the left child and the right child. That is, it is a <a href="/facts/M-ary_tree/XAMJC3QW">k-ary tree</a> with k = 2. A <a href="/facts/Recursive_definition/9RfhFw0R">recursive definition</a> using <a href="/facts/Set_theory/1ptfsvUP">set theory</a> is that a binary tree is a <a href="/facts/Tuple/BI1HIxL8">tuple</a> (L, S, R), where L and R are binary trees or the <a href="/facts/Empty_set/ffEk3eA6">empty set</a> and S is a <a href="/facts/Singleton_set/LtNVfujT">singleton set</a> containing the root.
From a <a href="/facts/Graph_theory/VVPCd4TX">graph theory</a> perspective, binary trees as defined here are <a href="/facts/Arborescence_(graph_theory)/qFKvoaLJ">arborescences</a>. A binary tree may thus be also called a bifurcating arborescence, a term which appears in some early programming books before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an <a href="/facts/Undirected_graph/kw3eIBUe">undirected</a>, rather than <a href="/facts/Directed_graph/YBdfQ0um">directed graph</a>, in which case a binary tree is an <a href="/facts/Ordered_tree/TCWk4Joy">ordered</a>, <a href="/facts/Rooted_tree/TCWk4Joy">rooted tree</a>. 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.
In mathematics, what is termed binary tree can vary significantly from author to author. Some use the definition commonly used in computer science, but others define it as every non-leaf having exactly two children and don't necessarily label the children as left and right either.
In computing, binary trees can be used in two very different ways:

<ul><li>First, as a means of accessing nodes based on some value or label associated with each node. Binary trees labelled this way are used to implement <a href="/facts/Binary_search_tree/gWubNt7b">binary search trees</a> and <a href="/facts/Binary_heap/YPJAEN94">binary heaps</a>, and are used for efficient <a href="/facts/Search_algorithm/eJuw0nyz">searching</a> and <a href="/facts/Sorting_algorithm/PwHpj1Gs">sorting</a>. 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. 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 <a href="/facts/Self-balancing_binary_search_tree/W7WAsES0">balancing</a>) without changing the meaning.</li>
<li>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 <a href="/facts/Huffman_coding/dBgMBz48">Huffman coding</a> and <a href="/facts/Cladograms/fWFYhUFo">cladograms</a>. The everyday division of documents into chapters, sections, paragraphs, and so on is an analogous example with n-ary rather than binary trees.</li></ul>

Binary tree open-in-new

Binary tree