Binary tree


In computer science, a binary tree is a tree data structure in which each node has at most two children, which are referred to as the ' and the '. A recursive definition using just set theory notions is that a binary tree is a tuple, where L and R are binary trees or the empty set and S is a singleton set containing the root. Some authors allow the binary tree to be the empty set as well.
From a graph theory perspective, binary trees as defined here are actually arborescences. A binary tree may thus be also called a bifurcating arborescence—a term which appears in some very old programming books, before the modern computer science terminology prevailed. It is also possible to interpret a binary tree as an undirected, rather than a 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. A binary tree is a special case of an ordered K-ary tree, where k is 2.
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 order the children either.
In computing, binary trees are used in two very different ways:

Recursive definition

To actually define a binary tree in general, we must allow for the possibility that only one of the children may be empty. 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:
Another way of imagining this construction is to consider instead of the empty set a different type of node—for instance square nodes if the regular ones are circles.

Using graph theory concepts

A binary tree is a rooted tree that is also an ordered tree in which every node has at most two children. A rooted tree naturally imparts a notion of levels, thus for every node a notion of children may be defined as the nodes connected to it a level below. Ordering of these children makes possible to distinguish left child from right child. But this still doesn't distinguish between a node with left but not a right child from a one with right but no left child.
The necessary distinction can be made by first partitioning the edges, i.e., defining the binary tree as triplet, where is a rooted tree and E1 ∩ E2 is empty, and also requiring that for all j ∈ every node has at most one Ej child. A more informal way of making the distinction is to say, quoting the Encyclopedia of Mathematics, that "every node has a left child, a right child, neither, or both" and to specify that these "are all different" binary trees.

Types of binary trees

Tree terminology is not well-standardized and so varies in the literature.
which maps to a perfect depth-4 binary tree.
In combinatorics one considers the problem of counting the number of full binary trees of a given size. Here the trees have no values attached to their nodes, and trees are distinguished only by their structure; however the left and right child of any node are distinguished. The size of the tree is taken to be the number n of internal nodes ; the other nodes are leaf nodes and there are of them. The number of such binary trees of size n is equal to the number of ways of fully parenthesizing a string of symbols separated by n binary operators, so as to determine the argument subexpressions of each operator. For instance for one has to parenthesize a string like, which is possible in five ways:
The correspondence to binary trees should be obvious, and the addition of redundant parentheses is disallowed.
There is a unique binary tree of size 0, and any other binary tree is characterized by the pair of its left and right children; if these have sizes i and j respectively, the full tree has size. Therefore, the number of binary trees of size n has the following recursive description, and for any positive integer n. It follows that 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 ; this number is therefore also the Catalan number. So there are also five Dyck words of length 6:
These Dyck words do not correspond to binary trees in the same way. 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. Any other Dyck word can be written as, where, are themselves Dyck words and where the two written parentheses are matched. The bijection is then defined by letting the words and 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 ; then the dotted-pair expression for that proper list is a fully parenthesized expression describing the corresponding binary tree.
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.

Methods for storing binary trees

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

Nodes and references

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. Sometimes it also contains a reference to its unique parent. If a node has fewer than two children, some of the child pointers may be set to a special null value, or to a special sentinel node.
This method of storing binary trees wastes a fair bit of memory, as the pointers will be null more than half the time; a more conservative representation alternative is threaded binary tree.
In languages with tagged unions such as ML, a tree node is often a tagged union of two types of nodes, one of which is a 3-tuple of data, left child, and right child, and the other of which is a "leaf" node, which contains no data and functions much like the null value in a language with pointers. For example, the following line of code in OCaml defines a binary tree that stores a character in each node.

type chr_tree = Empty | Node of char * chr_tree * chr_tree

Arrays

Binary trees can also be stored in breadth-first order as an implicit data structure in arrays, and if the tree is a complete binary tree, this method wastes no space. In this compact arrangement, if a node has an index i, its children are found at indices and , while its parent is found at index . This method benefits from more compact storage and better locality of reference, particularly during a preorder traversal. However, it is expensive to grow and wastes space proportional to 2h - n for a tree of depth h with n nodes.
This method of storage is often used for binary heaps.

Encodings

Succinct encodings

A succinct data structure is one which occupies close to minimum possible space, as established by information theoretical lower bounds. The number of different binary trees on nodes is, the th Catalan number. For large, this is about ; thus we need at least about bits to encode it. A succinct binary tree therefore would occupy bits.
One simple representation which meets this bound is to visit the nodes of the tree in preorder, outputting "1" for an internal node and "0" for a leaf. If the tree contains data, we can simply simultaneously store it in a consecutive array in preorder. This function accomplishes this:
function EncodeSuccinct
The string structure has only bits in the end, where is the number of nodes; we don't even have to store its length. To show that no information is lost, we can convert the output back to the original tree like this:
function DecodeSuccinct
More sophisticated succinct representations allow not only compact storage of trees but even useful operations on those trees directly while they're still in their succinct form.

Encoding general trees as binary trees

There is a one-to-one mapping between general ordered trees and binary trees, which in particular is used by Lisp to represent general ordered trees as binary trees. To convert a general ordered tree to binary tree, we only need to represent the general tree in left-child right-sibling way. The result of this representation will automatically be a binary tree, if viewed from a different perspective. Each node N in the ordered tree corresponds to a node N' in the binary tree; the left child of N' is the node corresponding to the first child of N, and the right child of N' is the node corresponding to N 's next sibling --- that is, the next node in order among the children of the parent of N. This binary tree representation of a general order tree is sometimes also referred to as a left-child right-sibling binary tree.
One way of thinking about this is that each node's children are in a linked list, chained together with their right fields, and the node only has a pointer to the beginning or head of this list, through its left field.
For example, in the tree on the left, A has the 6 children. It can be converted into the binary tree on the right.


The binary tree can be thought of as the original tree tilted sideways, with the black left edges representing first child and the blue right edges representing next sibling. The leaves of the tree on the left would be written in Lisp as:
which would be implemented in memory as the binary tree on the right, without any letters on those nodes that have a left child.

Common operations

There are a variety of different operations that can be performed on binary trees. Some are mutator operations, while others simply return useful information about the tree.

Insertion

Nodes can be inserted into binary trees in between two other nodes or added after a leaf node. In binary trees, a node that is inserted is specified as to which child it is.

Leaf nodes

To add a new node after leaf node A, A assigns the new node as one of its children and the new node assigns node A as its parent.

Internal nodes

Insertion on internal nodes is slightly more complex than on leaf nodes. Say that the internal node is node A and that node B is the child of A. A assigns its child to the new node and the new node assigns its parent to A. Then the new node assigns its child to B and B assigns its parent as the new node.

Deletion

Deletion is the process whereby a node is removed from the tree. Only certain nodes in a binary tree can be removed unambiguously.

Node with zero or one children

Suppose that the node to delete is node A. If A has no children, deletion is accomplished by setting the child of A's parent to null. If A has one child, set the parent of A's child to A's parent and set the child of A's parent to A's child.

Node with two children

In a binary tree, a node with two children cannot be deleted unambiguously. However, in certain binary trees these nodes can be deleted, though with a rearrangement of the tree structure.

Traversal

Pre-order, in-order, and post-order traversal visit each node in a tree by recursively visiting each node in the left and right subtrees of the root.

Depth-first order

In depth-first order, we always attempt to visit the node farthest from the root node that we can, but with the caveat that it must be a child of a node we have already visited. 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. Pre-order is a special case of this. See depth-first search for more information.

Breadth-first order

Contrasting with depth-first order is breadth-first order, which always attempts to visit the node closest to the root that it has not already visited. See breadth-first search for more information. Also called a level-order traversal.
In a complete binary tree, a node's breadth-index can be used as traversal instructions from the root. Reading bitwise from left to right, starting at bit d − 1, where d is the node's distance from the root and the node in question is not the root itself. When the breadth-index is masked at bit d − 1, the bit values 0 and 1 mean to step either left or right, respectively. The process continues by successively checking the next bit to the right until there are no more. The rightmost bit indicates the final traversal from the desired node's parent to the node itself. 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.

Citations