Possible database queries for binary trees: search your data / browse all statistics / browse all maps
1. Definition & Example
A binary tree is a rooted tree where each node is either internal (has two children) or is a leaf (has no children).
Equivalently, a binary tree is recursively defined to be either an empty tree (leaf) or an ordered pair of binary trees (internal node).
The five binary trees with 3 internal nodes |
||||
|
|
|
|
|
[.,[.,[.,.]]] |
[.,[[.,.],.]] |
[[.,.],[.,.]] |
[[.,[.,.]],.] |
[[[.,.],.],.] |
![http://www.findstat.org/Graphics/api/Cc0010_0_[.,[.,[.,.]]].png](http://www.findstat.org/Graphics/api/Cc0010_0_[.,[.,[.,.]]].png "http://www.findstat.org/Graphics/api/Cc0010_0_[.,[.,[.,.]]].png")
![http://www.findstat.org/Graphics/api/Cc0010_0_[.,[[.,.],.]].png](http://www.findstat.org/Graphics/api/Cc0010_0_[.,[[.,.],.]].png "http://www.findstat.org/Graphics/api/Cc0010_0_[.,[[.,.],.]].png")
![http://www.findstat.org/Graphics/api/Cc0010_0_[[.,.],[.,.]].png](http://www.findstat.org/Graphics/api/Cc0010_0_[[.,.],[.,.]].png "http://www.findstat.org/Graphics/api/Cc0010_0_[[.,.],[.,.]].png")
![http://www.findstat.org/Graphics/api/Cc0010_0_[[.,[.,.]],.].png](http://www.findstat.org/Graphics/api/Cc0010_0_[[.,[.,.]],.].png "http://www.findstat.org/Graphics/api/Cc0010_0_[[.,[.,.]],.].png")
![http://www.findstat.org/Graphics/api/Cc0010_0_[[[.,.],.],.].png](http://www.findstat.org/Graphics/api/Cc0010_0_[[[.,.],.],.].png "http://www.findstat.org/Graphics/api/Cc0010_0_[[[.,.],.],.].png")
- The graphical representation omits the leafs and only shows the internal nodes.
There are $\operatorname{Cat}(n) = \frac{1}{n+1}\binom{2n}{n}$ binary trees with $n$ internal nodes, see OEIS:A000108.
2. FindStat representation and coverage
A binary tree is uniquely represented as a dot (empty tree) or as a sorted list of binary trees.
Binary trees are graded by the number of internal nodes.
- The database contains all binary trees of size at most 8.
3. Additional information
Feel free to add further information on the combinatorics of binary trees here!
4. References
5. Sage examples