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

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.

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.

Binary Tree Media

• 

  A labeled binary tree of size 9 (the number of nodes in the tree) and height 3 (the height of a tree defined as the number of edges or links from the top-most or root node to the farthest leaf node), with a root node whose value is 1. The above tree is unbalanced and not sorted.

• 

  An image of a full binary tree.

• 

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

• 

  A small complete binary tree stored in an array

• 

  An example of converting an n-ary tree to a binary tree

• 

  Tree rotations are very common internal operations on self-balancing binary trees.

• 

  The process of inserting a node into a binary tree

• 

  The process of deleting an internal node in a binary tree

Traversals

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

The current item is visited, then the left branch is visited, and then the right branch is visited. <syntaxhighlight lang="java"> void preOrder(Item item) {

   if (item == null) return;
   visit(item);
   preOrder(item.left);
   preOrder(item.right);

} </syntaxhighlight>

In-order

The left branch is visited, then the current item is visited, and then the right branch is visited. <syntaxhighlight lang="java"> void inOrder(Item item) {

   if (item == null) return;
   inOrder(item.left);
   visit(item);
   inOrder(item.right);

} </syntaxhighlight>

Post-order

The left branch is visited, the right branch is visited, and then the current item is visited. <syntaxhighlight lang="java"> void postOrder(Item item) {

   if (item == null) return;
   postOrder(item.left);
   postOrder(item.right);
   visit(item);

} </syntaxhighlight>