In computer science, a binary tree is a tree data structure in which each node has at most two children, referred to as the left child and the right child. That is, it is a k-ary tree where k = 2. A recursive definition using set theory is that a binary tree is a triple (L, S, R), where L and R are binary trees or the empty set and S is a singleton (a single–element set) containing the root.

From a graph theory perspective, binary trees as defined here are arborescences. A binary tree may thus be also called a bifurcating arborescence, a term which appears in some early programming books before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an undirected, rather than directed graph, in which case a binary tree is an ordered, rooted tree. Some authors use rooted binary tree instead of binary tree to emphasize the fact that the tree is rooted, but as defined above, a binary tree is always rooted.

In mathematics, what is termed binary tree can vary significantly from author to author. Some use the definition commonly used in computer science, but others define it as every non-leaf having exactly two children and don't necessarily label the children as left and right either.

In computing, binary trees can be used in two very different ways:

A simple, informal approach to describe a binary tree might be as follows:

More formally:

This definition implies two limitations: a full binary tree contains at least one node, and no node can have only one child. This is resolved with the next definition.

The extended tree definition starts with the assumption the tree can be empty.