Editing Binary tree (section)

=== 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>