Binary tree

[1][2] From a graph theory perspective, binary trees as defined here are arborescences.

[3] A binary tree may thus be also called a bifurcating arborescence,[3] a term which appears in some early programming books[4] before the modern computer science terminology prevailed.

An artifact, which in some textbooks is called an extended binary tree, is needed for that purpose.

An extended binary tree is thus recursively defined as:[11] Another way of imagining this construction (and understanding the terminology) is to consider instead of the empty set a different type of node—for instance square nodes if the regular ones are circles.

A rooted tree naturally imparts a notion of levels (distance from the root); thus, for every node, a notion of children may be defined as the nodes connected to it a level below.

The necessary distinction can be made by first partitioning the edges; i.e., defining the binary tree as triplet (V, E1, E2), where (V, E1 ∪ E2) is a rooted tree (equivalently arborescence) and E1 ∩ E2 is empty, and also requiring that for all j ∈ { 1, 2 }, every node has at most one Ej child.

In combinatorics, one considers the problem of counting the number of full binary trees of a given size.

The number of such binary trees of size n is equal to the number of ways of fully parenthesizing a string of n + 1 symbols (representing leaves) separated by n binary operators (representing internal nodes), to determine the argument subexpressions of each operator.

⁠, which is possible in five ways: The correspondence to binary trees should be obvious, and the addition of redundant parentheses (around an already parenthesized expression or around the full expression) is disallowed (or at least not counted as producing a new possibility).

is the Catalan number of index n. The above parenthesized strings should not be confused with the set of words of length 2n in the Dyck language, which consist only of parentheses in such a way that they are properly balanced.

The number of such strings satisfies the same recursive description (each Dyck word of length 2n is determined by the Dyck subword enclosed by the initial '(' and its matching ')' together with the Dyck subword remaining after that closing parenthesis, whose lengths 2i and 2j satisfy i + j + 1 = n); this number is therefore also the Catalan number

Instead, they are related by the following recursively defined bijection: the Dyck word equal to the empty string corresponds to the binary tree of size 0 with only one leaf.

are themselves (possibly empty) Dyck words and where the two written parentheses are matched.

correspond to the binary trees that are the left and right children of the root.

A bijective correspondence can also be defined as follows: enclose the Dyck word in an extra pair of parentheses, so that the result can be interpreted as a Lisp list expression (with the empty list () as only occurring atom); then the dotted-pair expression for that proper list is a fully parenthesized expression (with NIL as symbol and '.'

as operator) describing the corresponding binary tree (which is, in fact, the internal representation of the proper list).

The ability to represent binary trees as strings of symbols and parentheses implies that binary trees can represent the elements of a free magma on a singleton set.

Binary trees can be constructed from programming language primitives in several ways.

In a language with records and references, binary trees are typically constructed by having a tree node structure which contains some data and references to its left child and its right child.

This method of storing binary trees wastes a fair bit of memory, as the pointers will be null (or point to the sentinel) more than half the time; a more conservative representation alternative is threaded binary tree.

For example, the following line of code in OCaml (an ML dialect) defines a binary tree that stores a character in each node.

In this compact arrangement, if a node has an index i, its children are found at indices

[28] This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal.

[29] A succinct data structure is one which occupies close to minimum possible space, as established by information theoretical lower bounds.

[30] If the tree contains data, we can simply simultaneously store it in a consecutive array in preorder.

This representation is called a left-child right-sibling binary tree.

If A has no children, deletion is accomplished by setting the child of A's parent to null.

Unlike a depth-first search on graphs, there is no need to remember all the nodes we have visited, because a tree cannot contain cycles.

In a complete binary tree, a node's breadth-index (i − (2d − 1)) can be used as traversal instructions from the root.

There is a time-space trade-off between iterating a complete binary tree this way versus each node having pointer(s) to its sibling(s).