# Algorithms Notes – Binary Trees

A binary tree.

Def: Let $T$ be a tree such that no node in $T$ has more than two children. $T$ is referred to as a binary tree.

A binary tree effectively consists of a root $r$ and two subtrees $T_{L}$ and $T_{R}$, any (or both) of which could be empty.

Since we already know the maximum number of children each node in a binary tree can have, we can implement it in a way that is very simple in comparison to the implementation of a general tree. Just store pointers for the two children in every node.

```struct Tree_Node
{
Element_Type Element;
Tree_Node* Left_Child;
Tree_Node* Right_Child;
};
```

Def: Let $T$ be a binary tree such that each node has either zero or exactly two children. $T$ is called a full binary tree.

Full Binary Tree

Def: Let $T$ be a binary tree such that every level of $T$ except for possibly the last is completely filled and all nodes are as far-left as possible. $T$ is called a complete binary tree.

Complete Binary Tree