Editing Binary tree (section)

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