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.

• 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.

A binary tree can be implemented using an array by storing its level-order traversal.^[1] 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.

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.

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);
}

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);
}

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);
}