A **binary tree** is a data structure composed of zero or more **nodes**. Each node contains:

- A
**value**(some kind of data item) - A reference or pointer to a
**left child**(may be null) - A reference or pointer to a
**right child**(may be null)

A binary tree may be **empty**, in which case it has no nodes. If it is not empty, a binary tree has a root node.

Every node in the binary tree is reachable from the root node by a unique path.

A node with neither a left child nor a right child is called a **leaf**.

The **size of a binary tree** is the number of nodes in it.

The **depth of a node** is its distance from the root.

The **depth of a binary tree** is the depth of its deepest node.

A binary tree is said to be **balanced** if every level above the lowest is “full” (contains 2N nodes). In most applications, a reasonably balanced binary tree is desirable.

**Next: Hash Tables**