Trees are very useful data structures. With little effort, we can think of several situations trees are useful for. Think of ancestry trees, your computer file system, and how about a tree of all possible solutions to a chess game.

### Definition

In their general form, **trees** are data structures in which data is stored in ** nodes**. Nodes are connected together with

**.**

*edges*

One thing to keep in mind, *there are no circles in trees.* In other words, you can only get from one node to another only by one *path*. In fact, if there are multiple paths between any two nodes the data structure becomes a *graph*, but let’s save this for another discussion.

### Rooted Trees

A *rooted* tree is a special case of trees in which we designate a node (any node) to be the ** root** of the tree. This helps with computers because it is convenient to have a consistent reference for your data structure, similar to the

*head*of a linked list.

In a rooted tree, every node has a ** parent** except the root.

Now we need to define more terms to be able to discuss trees fluently:

- A
**path**is any sequence of connected edges. - A node p has a
**child**node c, if c is the first node encountered on a path from p. - A
**leaf**is a node with no children. **Siblings**are all nodes with the same parent.**Ancestors**are all nodes on a path from node n to root. Including n. Think of a family tree.**Length**of a path is the number of*edges*in that path.**Depth**of a node n is the length of the path from n to the root.**Height**of a node n is the length of path from n to its deepest leaf. The*height of a tree*is the height of the root.

The diagram below helps you visualize the definitions above.

After observing the rooted tree diagram, we could imagine many applications to make use of trees. Also, from the diagram, we could envision a simple way to represent trees in computers and have computers do very interesting stuff using trees.

In the next post, we will discuss implementing trees in code. Then we will define several ways to iterate though or *traverse* a tree.

Stay tuned in to discuss tree types and how to make the best use of computer time and space using trees.