Trees

A tree is an abstract data type representing a hierarchical collection of elements. Each element has a parent element (except the root node) and zero or more child elements.

Nodes with the same parent are called siblings. Nodes are called internal if they have at least one child, and are called leaves if they have no children.

The link from a node to a child is called an edge.

The depth of a node is the number of edges from the root node to the node (the root node has depth 0).

All nodes with the same depth form a level.

The height of a tree is the largest depth of any node.

Binary trees

A binary tree is a tree where each node can have up to two children, called a left child and a right child.

A binary tree is called full if all nodes have either 0 or 2 children.

A binary tree is called complete if all levels (except possibly the last level) are completely full, and all nodes in the last level are as far left as possible.

A binary tree is called perfect if all internal nodes have 2 children and all leaves are at the same level.