Cette structure de données est définie de façon récursive : un arbre binaire est soit l'arbre vide, soit formé de deux arbres binaires, appelés fils gauche et fils droit.
Les arbres que l'on utilise en informatique sont de plus étiquetés par des objets (dans les exemple qui suivent, ces objets seront des entiers, mais les étiquettes peuvent être de n'importe quel type) : un arbre binaire étiqueté est soit l'arbre vide, soit formé d'une étiquette et de deux arbres binaires étiquetés, appelés fils gauche et fils droit. Un sous-arbre d'un arbre est soit un fils, soit un sous-arbre d'un fils. Un arbre vide n'a pas de sous-arbre.
La figure suivante représente un arbre binaire étiqueté par des entiers, ce qu'on abrégera par la suite en << arbre >>.
Figure: Arbre binaire étiqueté
Cet arbre est non vide ; il a donc une racine, étiquetée par 1,
et deux fils. Les racines des sous-arbres sont les n 
uds de
l'arbre ; cet arbre a 13 n uds. Les feuilles d'un arbre sont
des sous-arbres dont les deux fils sont des arbres vides; les feuilles
de cet arbre sont étiquetées par 8, 5, 9, 12, 13, 11.