---
tag: 02A8EMC83C
kind: definition
name: Binary tree
msc: [05C05]
defines: 0D7EZ10V2R
sources:
  - url: https://en.wikipedia.org/wiki/Binary_tree
    locator: Recursive definition
---

## 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|0Y97E2DMB7]] states this.
A nonempty binary tree is a [[rooted tree|0C9J6W2A8A]] 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.