A binary tree is a tree data structure where each node has a left and a right child.

# Terminology

• A rooted binary tree has a root node and every node has at most two children.
• A full binary tree is a tree where every node has either or children.
• A perfect binary tree is a binary tree where all nodes have two children and all leaves have the same depth.
• A complete binary tree has every level filled except possibly the last and all the nodes in the last level are as far left as possible. It can have between and nodes where is the height of the tree.
• An infinite complete binary tree is a tree where every node has two children and the depth is countably infinite.
• A balanced binary tree is a binary tree where the left and right subtrees of every node differ in height by no more than .
• A degenerate binary tree is a tree where each parent node has only one child node.

# Properties

• The number of nodes in a full binary tree is at least and at most where is the height of the tree. A tree with only a root node has a height of .
• The number of leaves in a perfect binary tree is because the number of non-leaf (internal) nodes is .
• A perfect binary tree with leaves has nodes.

# Representing with Arrays

A binary tree can be represented using an array data structure. In case the tree is complete then this method does not waste any space.

The index of the left-node is given by:

The index of the right-node is given by:

The index of the parent of a node is given by:

where:

• is the largest interger less than or equal to .