# Binary tree facts for kids

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

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

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

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

*Kiddle Encyclopedia.*