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

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

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

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 .

fuss/data_structures/trees/binary_trees.txt ยท Last modified: 2017/02/22 18:30 (external edit)

For the copyright, license, warranty and privacy terms for the usage of this website please see the license, privacy and plagiarism pages.