Editing Binary tree (section)

== Definitions ==

=== Recursive definition ===
{{section rewrite|date=July 2014}}
To define a binary tree, the possibility that only one of the children may be empty must be acknowledged. An [[Artifact (software development)|artifact]], which in some textbooks is called an ''extended binary tree,'' is needed for that purpose. An extended binary tree is thus recursively defined as:<ref name="Rosen2011"/>
* the [[empty set]] is an extended binary tree
* if T<sub>1</sub> and T<sub>2</sub> are extended binary trees, then denote by T<sub>1</sub> • T<sub>2</sub> the extended binary tree obtained by {{Clarify|date=May 2020|post-text=where did the 'r' go in the 'T<sub>1</sub> • T<sub>2</sub>' symbol|text=adding a root ''r'' connected to the left to T<sub>1</sub> and to the right to T<sub>2</sub>}} by adding edges when these sub-trees are non-empty.

Another way of imagining this construction (and understanding the terminology) is to consider instead of the empty set a different type of node—for instance square nodes if the regular ones are circles.<ref name="HuShing2002">{{cite book|author1=Te Chiang Hu|author2=Man-tak Shing|title=Combinatorial Algorithms |year=2002 |publisher=Courier Dover Publications| isbn=978-0-486-41962-6|page=162}}</ref>

=== Using graph theory concepts ===
A binary tree is a [[rooted tree]] that is also an [[ordered tree]] (a.k.a. plane tree) in which every node has at most two children. A rooted tree naturally imparts a notion of levels (distance from the root); thus, for every node, a notion of children may be defined as the nodes connected to it a level below. Ordering of these children (e.g., by drawing them on a plane) makes it possible to distinguish a left child from a right child.<ref name="HsuLin2008">{{cite book|author1=Lih-Hsing Hsu| author2=Cheng-Kuan Lin|title=Graph Theory and Interconnection Networks|url=https://books.google.com/books?id=vbxdqhDKOSYC&pg=PA66|date=2008| publisher=CRC Press|isbn=978-1-4200-4482-9|page=66}}</ref> But this still does not distinguish between a node with left but not a right child from a node with right but no left child.

The necessary distinction can be made by first partitioning the edges; i.e., defining the binary tree as triplet (V, E<sub>1</sub>, E<sub>2</sub>), where (V, E<sub>1</sub> ∪ E<sub>2</sub>) is a rooted tree (equivalently arborescence) and E<sub>1</sub> ∩ E<sub>2</sub> is empty, and also requiring that for all ''j'' ∈ { 1, 2 }, every node has at most one E<sub>''j''</sub> child.<ref name="FlumGrohe2006">{{cite book|author1=J. Flum| author2=M. Grohe| author2-link=Martin Grohe| title=Parameterized Complexity Theory| year=2006| publisher=Springer|isbn=978-3-540-29953-0|page=245}}</ref> A more informal way of making the distinction is to say, quoting the [[Encyclopedia of Mathematics]], that "every node has a left child, a right child, neither, or both" and to specify that these "are all different" binary trees.<ref name="oem">{{SpringerEOM| id=Binary_tree&oldid=31607|title=Binary tree}} also in print as {{cite book| author=Michiel Hazewinkel|title=Encyclopaedia of Mathematics. Supplement I| url=https://books.google.com/books?id=3ndQH4mTzWQC&pg=PA124| year=1997|publisher=Springer Science & Business Media|isbn=978-0-7923-4709-5|page=124}}</ref>