Trees

A tree is a type of graph.

Each node has a value.

In a binary tree, each node has two children (traditionally left and right) and one parent.

There is a scheme for representing trees with arbitrary numbers of children using only $O(n)$ space. Each node contains

• a pointer pointing to it's parent,
• a pointer pointing to it's left-most child, and
• a pointer pointing to it's sibling immeadiately to the right.