# Tree

A tree is a recursive data structure with a single root node and zero or more child nodes. It is also a special case of graph. Each link between a node is called an edge.

## Properties of trees

- Depth of a node: The number of edges between the node and the root node.
- Height: The number of edges between the root node and the furthest leaf node. This is the same as the depth of the furthest leaf node.
- Width:
- Balance:

## Types of Trees

### Binary trees

There are a few types of binary trees.

- Perfect
- Full
- Complete
- Binary search tree

In a perfect binary tree, the number of nodes is `log(height + 1)`

.

## Traversing Trees

- In order: Visits left child, current node, then right child. It is called "In order" because in a binary search tree, this would visit each node in order.
- Pre order: Visits current node, left child, right child.
- Post order: Visits left child, right child, current node.