Editing Binary tree (section)

== Types of binary trees ==
Tree terminology is not well-standardized and therefore may vary among examples in the available literature.
* A '''{{visible anchor|rooted}}''' binary [[tree data structure|tree]] has a [[root node]] and every node has at most two children.
[[File:Full binary.svg|thumbnail|A full binary tree]]
[[File:Waldburg Ahnentafel.jpg|thumb|An [[ancestry chart]] which can be mapped to a perfect 4-level binary tree.]]
* A '''{{visible anchor|full}}''' binary tree (sometimes referred to as a '''proper''',<ref>{{cite book|last1=Tamassia|first1=Michael T. Goodrich, Roberto |title=Algorithm design : foundations, analysis, and Internet examples| date=2011| publisher=Wiley-India|location=New Delhi| isbn=978-81-265-0986-7| page=76|edition=2|ref=Goodrich}}</ref> '''plane''', or '''strict''' binary tree)<ref>{{cite web| url=http://xlinux.nist.gov/dads/HTML/fullBinaryTree.html | title=full binary tree | publisher = [[NIST]]}}</ref><ref>Richard Stanley, Enumerative Combinatorics, volume 2, p.36</ref> is a tree in which every node has either 0 or 2 children. Another way of defining a full binary tree is a [[recursive definition]]. A full binary tree is either:<ref name="Rosen2011">{{cite book|author=Kenneth Rosen| title=Discrete Mathematics and Its Applications 7th edition| year=2011| publisher=McGraw-Hill Science|pages=352–353|isbn=978-0-07-338309-5}}</ref>
** A single vertex (a single node as the root node).
** A tree whose root node has two subtrees, both of which are full binary trees.
* A '''{{visible anchor|perfect}}''' binary tree is a binary tree in which all interior nodes have two children ''and'' all leaves have the same ''depth'' or same ''level'' (the level of a node defined as the number of edges or links from the root node to a node).<ref>{{cite web| url=https://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html|title=perfect binary tree | publisher = [[NIST]]}}</ref> A perfect binary tree is a full binary tree.
* A '''{{visible anchor|complete}}''' binary tree is a binary tree in which every level, ''except possibly the last'', is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2<sup>''h''</sup> nodes at the last level ''h''.<ref name="complete binary tree">{{cite web| url=https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html|title=complete binary tree| publisher = NIST}}</ref> A perfect tree is therefore always complete but a complete tree is not always perfect.  Some authors use the term '''complete''' to refer instead to a '''perfect''' binary tree as defined above, in which case they call this type of tree (with a possibly not filled last level) an '''almost complete''' binary tree or '''nearly complete''' binary tree.<ref name="almost complete binary tree">{{cite web| url=http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html|title=almost complete binary tree|access-date=2015-12-11|archive-url=https://web.archive.org/web/20160304081430/http://faculty.cs.niu.edu/~mcmahon/CS241/Notes/bintree.html|archive-date=2016-03-04|url-status=dead}}</ref><ref name="nearly complete binary tree">{{cite web |url=http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/nearly_complete.pdf |archive-url=https://ghostarchive.org/archive/20221009/http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/nearly_complete.pdf |archive-date=2022-10-09 |url-status=live| title=nearly complete binary tree}}</ref> A complete binary tree can be efficiently represented using an array.<ref name="complete binary tree"/>

[[File:Complete binary2.svg|alt=|thumb|A complete binary tree (that is not full)]]

* The '''infinite complete''' binary tree is a tree with <math>{\aleph_0}</math> levels, where for each level ''d'' the number of existing nodes at level d is equal to 2<sup>''d''</sup>. The cardinal number of the set of all levels is <math>{\aleph_0}</math> (countably infinite). The cardinal number of the set of all paths (the "leaves", so to speak) is uncountable, having the [[cardinality of the continuum]].
* A '''balanced''' binary tree is a binary tree structure in which the left and right subtrees of every node differ in height (the number of edges from the top-most node to the farthest node in a subtree) by no more than 1 (or the skew is no greater than 1).<ref>Aaron M. Tenenbaum, et al. Data Structures Using C, Prentice Hall, 1990 {{ISBN|0-13-199746-7}}</ref> One may also consider binary trees where no leaf is much farther away from the root than any other leaf. (Different balancing schemes allow different definitions of "much farther".<ref>Paul E. Black (ed.), entry for ''data structure'' in ''[[Dictionary of Algorithms and Data Structures]]''. U.S. [[National Institute of Standards and Technology]]. 15 December 2004. [http://xw2k.nist.gov/dads//HTML/balancedtree.html Online version] {{webarchive |url=https://web.archive.org/web/20101221085950/http://xw2k.nist.gov/dads/ |date=December 21, 2010 }} Accessed 2010-12-19.</ref>)
* A '''degenerate''' (or '''pathological''') tree is where each parent node has only one associated child node.<ref>{{Cite web|url=https://towardsdatascience.com/5-types-of-binary-tree-with-cool-illustrations-9b335c430254|title=Different Types of Binary Tree with colourful illustrations|last=Parmar|first=Anand K.|date=2020-01-22 |website=Medium|language=en|access-date=2020-01-24}}</ref> This means that the tree will behave like a [[linked list]] data structure. In this case, an advantage of using a binary tree is significantly reduced because it is essentially a linked list which [[time complexity]] is O(''n'') (''n'' as the number of nodes and 'O()' being the [[Big O notation]]) and it has more data space than the linked list due to two pointers per node, while the complexity of {{nowrap|O(log<sub>2</sub> ''n'')}} for data search in a balanced binary tree is normally expected.