Binary tree

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.