Рекурсивное определение

Существует следующее рекурсивное определение двоичного дерева (см. БНФ):

То есть двоичное дерево либо является пустым, либо состоит из данных и двух поддеревьев (каждое из которых может быть пустым). Очевидным, но важным для понимания фактом является то, что каждое поддерево в свою очередь тоже является деревом. Если у некоторого узла оба поддерева пустые, то он называется листовым узлом (листовой вершиной) или терминальным элементом.

Например, показанное справа на рис. 1 дерево, согласно этой грамматике можно было бы записать так:

(m (e (c (a nil nil) nil) (g nil (k nil nil))) (s (p (o nil nil) (s nil nil)) (y nil nil)))

Рис. 1. Двоичное дерево поиска, в котором ключами являются латинские символы упорядоченные по алфавиту.

Каждый узел в дереве задаёт поддерево, корнем которого он является. У вершины m=(data, left, right) есть два потомка (левый и правый) left и right и, соответственно, два поддерева (левое и правое) с корнями left и right.