Binary tree

Definition

The binary trees are defined recursively by these two rules. The empty tree is a binary tree. It has no nodes. If $L$ and $R$ are binary trees, then $\operatorname{node}(L, R)$ is a binary tree. It has one more node than $L$ and $R$ together, the root, with left subtree $L$ and right subtree $R$. Every binary tree comes from these two rules in a unique way, in finitely many steps.

Remarks

The left and right subtrees are ordered. Thus $\operatorname{node}(\operatorname{node}(\varnothing, \varnothing), \varnothing)$ and $\operatorname{node}(\varnothing, \operatorname{node}(\varnothing, \varnothing))$ are different binary trees with $2$ nodes. The number of binary trees with $n$ nodes is the Catalan number $C_n$. The node binary trees are counted by Catalan numbers states this. A nonempty binary tree is a rooted tree in which each vertex has at most two children, each marked left or right.

Explanations

L1 human

A binary tree is either empty, or a root with a left part and a right part that are binary trees again. Binary trees are used in computer science to store data for fast search.