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