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.
binary tree is a tree where every node has either
A perfect binary tree is a binary tree where all nodes have two children and all leaves have the same depth.
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
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.
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
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
binary tree with
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:
is the largest interger less than or equal to