Binary tree

In computer science, a binary tree is a type of tree (data structure) where each item 
within the tree has at most two children.

Types of binary trees
alt=|thumb|A complete binary tree which is not full.
 In a balanced binary tree the left and right branches of every item differ in height by no more than 1.
 In a complete binary tree every level, except possibly the last, is completely filled, and all items in the last level are as far left as possible.
 In a full binary tree every item has either 0 or 2 children.
 In a perfect binary tree all interior items have two children and all leaves have the same depth or same level. A perfect binary tree is also a full and complete binary tree.

Representations

Array
A binary tree can be implemented using an array by storing its level-order traversal. In a zero-indexed array, the root is often stored at index 1.

For the nth item of the array its:
 left child is stored at the 2n index.
 right child is stored at the 2n+1 index.
 parent is stored at the n/2 index.

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

Traversals
Pre-order (red): 
In-order (yellow): 
Post-order (green): 

Pre-order
The current item is visited, then the left branch is visited, and then the right branch is visited.
void preOrder(Item item) {
    if (item == null) return;
    visit(item);
    preOrder(item.left);
    preOrder(item.right);
}

In-order
The left branch is visited, then the current item is visited, and then the right branch is visited.
void inOrder(Item item) {
    if (item == null) return;
    inOrder(item.left);
    visit(item);
    inOrder(item.right);
}

Post-order
The left branch is visited, the right branch is visited, and then the current item is visited.
void postOrder(Item item) {
    if (item == null) return;
    postOrder(item.left);
    postOrder(item.right);
    visit(item);
}

References

Category:Data structures