Binary tree facts for kids

A binary tree is a special way to organize information in computer science. Imagine it like a family tree, but each "person" (which we call a node or item) can have at most two "children" (or connections) branching off from them. This structure helps computers store and find data very efficiently.

Types of Binary Trees

Binary trees come in different shapes and sizes. Here are a few common types:

• A balanced binary tree is like a well-balanced scale. The left and right sides of any item in the tree won't be too different in height. This helps keep the tree efficient.
• A complete binary tree is almost completely filled. All levels, except possibly the very last one, are full. Any items on the last level are packed as far left as they can be.
• In a full binary tree, every item either has no children at all, or it has exactly two children. You won't find any items with just one child.
• A perfect binary tree is a very neat tree. All items inside the tree have two children, and all the "leaf" items (those at the very bottom with no children) are on the same level. A perfect binary tree is both a full and a complete binary tree.

A complete binary tree which is not full.

How Binary Trees are Stored

Computers need ways to store these tree structures. Here are two main methods:

Using an Array

One way to store a binary tree is by putting its items into a simple list, called an array. Imagine the items are stored row by row, from top to bottom, and left to right.

If the first item in the array is at position 1 (some lists start at 0, others at 1), then:

• The left child of an item at position n is found at position 2n.
• The right child of an item at position n is found at position 2n+1.
• The parent of an item at position n is found at position n/2.

Using References

In many programming languages, binary trees are built using "references." This means each item in the tree has pointers or links that directly tell the computer where its left child and right child are located in memory. It's like each person in our family tree example knows exactly where their two children are sitting.

Walking Through a Binary Tree (Traversals)

When you want to look at all the items in a binary tree, you need a specific path to follow. This path is called a traversal. There are three main ways to "walk" through a binary tree:

Traversals of an example tree:
Pre-order (red): F, B, A, D, C, E, G, I, H
In-order (yellow): A, B, C, D, E, F, G, H, I
Post-order (green): A, C, E, D, B, H, I, G, F

Pre-order Traversal

In a pre-order traversal, you visit the current item first. Then, you move to its left branch and visit everything there. Finally, you go to its right branch and visit everything there.

This is useful when you want to make a copy of the tree or see the items in a specific order.

void preOrder(Item item) {
    if (item == null) return; // If there's no item, stop.
    visit(item);             // Do something with the current item.
    preOrder(item.left);     // Go to the left child.
    preOrder(item.right);    // Go to the right child.
}

In-order Traversal

For an in-order traversal, you first visit everything in the left branch. After that, you visit the current item itself. Lastly, you visit everything in the right branch.

If your binary tree is set up in a special way (like a binary search tree), an in-order traversal will list the items in alphabetical or numerical order.

void inOrder(Item item) {
    if (item == null) return; // If there's no item, stop.
    inOrder(item.left);      // Go to the left child.
    visit(item);             // Do something with the current item.
    inOrder(item.right);     // Go to the right child.
}

Post-order Traversal

In a post-order traversal, you visit everything in the left branch first. Then, you visit everything in the right branch. Only after both branches are done do you visit the current item.

This type of traversal is often used when you need to delete items from a tree, starting from the bottom.

void postOrder(Item item) {
    if (item == null) return; // If there's no item, stop.
    postOrder(item.left);    // Go to the left child.
    postOrder(item.right);   // Go to the right child.
    visit(item);             // Do something with the current item.
}

Images for kids

• 

  An ancestry chart which can be mapped to a perfect 4-level binary tree.

See also

In Spanish: Árbol binario para niños