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.
Contents
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 levelorder traversal. In a zeroindexed 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
Preorder
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);
}
Inorder
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);
}
Postorder
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);
}
Images for kids

An ancestry chart which can be mapped to a perfect 4level binary tree.
See also
In Spanish: Árbol binario para niños