Saindra Santyadiputra

In computer science, a binary tree is a tree data structure in which each node has at most two children. Typically the first node is known as the parent and the child nodes are called left and right. In type theory, a binary tree with nodes of type A is defined inductively as TA = μα. 1 + A × α × α. Binary trees are commonly used to implement binary search trees and binary heaps.

Graph theorists use the following definition: A binary tree is a connected acyclic graph such that the degree of each vertex is no more than 3. It can be shown that in any binary tree, there are exactly two more nodes of degree one than there are of degree three, but there can be any number of nodes of degree two. A rooted binary tree is such a graph that has one of its vertices of degree no more than 2 singled out as the root.

With the root thus chosen, each vertex will have a uniquely defined parent, and up to two children; however, so far there is insufficient information to distinguish a left or right child. If we drop the connectedness requirement, allowing multiple connected components in the graph, we call such a structure a forest.

Another way of defining binary trees is a recursive definition on directed graphs. A binary tree is either:

This also does not establish the order of children, but does fix a specific root node.

The groupings of pairs of nodes in a tree can be represented as pairs of letters, surrounded by parenthesis. Thus, (a b) denotes the binary tree whose left subtree is a and whose right subtree is b. Strings of balanced pairs of parenthesis may therefore be used to denote binary trees in general. The set of all possible strings consisting entirely of balanced parentheses is known as the Dyck language.

Given n nodes, the total number of ways in which these nodes can be arranged into a binary tree is given by the Catalan number Cn. For example, C2 = 2 declares that (a 0) and (0 a) are the only binary trees possible that have two nodes, and C3 = 5 declares that ((a 0) 0), (0 a) 0), (0 (a 0)), (0 (0 a)), and (a b) are the only five binary trees possible that have 3 nodes. Here 0 represents a subtree that is not present.

The ability to represent binary trees as strings of symbols and parentheses implies that binary trees can represent the elements of a magma. Conversely, the set of all possible binary trees, together with the natural operation of attaching trees to one-another, forms a magma, the free magma.

Given a string representing a binary tree, the operators to obtain the left and right subtrees are sometimes referred to as car and cdr.