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. Additional information
Feel free to add further information on the combinatorics of binary trees here!
3. References
4. Sage examples
5. Technical information for database usage
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.