# Trees

A Tree is a data structure.

The **Tree** is a data structure particularly good at representing
hierarchical relationships. Unlike linear data structures such as linked
lists, trees model a parent-child structure. Common examples include family
trees, organizational charts, filesystem directories, and the chapter
structure of a book. They, and other tree-based logic, are very, very common. In other words, it'll be important to not only understand how trees (the data structure) work, but also to get used to thinking in a tree-like way.

![Flowchart Example](flowchart.jpg)

Just like how all linked list nodes are (eventually) accessible from a single
`head` node, a tree's elements, also stored in nodes, are eventually
accessible from a single top-most node, known as the **root**.

## Terminology

To discuss trees, we use the following standard terminology:

* **Node**: An element within the tree.
* **Root**: The single node at the top of the tree, which has no parent.
* **Parent**: For two nodes A and B, A is the *parent* of B if A is directly above B in the hierarchy and connected to it. Each node has at most one parent.
* **Child**: The inverse of a parent. If A is the parent of B, then B is the child of A.
* **Sibling**: Two nodes are siblings if they share the same parent.
* **Ancestor**: A node's parent, its parent's parent, and so on, up to the root.
* **Descendant**: A node's children, its children's children, and so on.
* **External Node (or Leaf)**: A node with no children.
* **Internal Node**: A node with one or more children.
* **Subtree**: A portion of a tree consisting of a node and all of its
 descendants. This portion is itself a valid tree!

![](recursion.jpg)

## Binary Trees

A very common example of a tree is the *binary* tree. As you might guess, a
binary tree has up to two children for each parent.  A binary tree built to
hold data might start being implemented like this:

```python
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinaryTree:
    def __init__(self):
        self.root = None
```

Here's a picture of such a tree:

![](treeIllus.png)

The **height** of a tree is the length of the path of the node furthest from
the root. The height of this tree is 3, because no node is more than three
links away from the root.

Trees have heights, but nodes have **depths**. This is the number of links
between the node and the root.

Let us think about how short a binary tree can be in order to store $n$ nodes.
If $n=1$, the tree has height 0. If $N$ is 2 or 3, the tree can be of height
1. A tree can have up to $n=7$, and still only be height 2.  This table
continues that thought process:

|Height|Maximum $n$|
|------|-----------|
|0     |1          |
|1|3|
|2|7|
|3|15|
|4|31|
|5|63|

Note that $n$ is essentially doubling each time we add another depth. This
demonstrates the main advantage of a Tree: while a Linked List takes $O(n)$ time
to get from the head to an arbitrary node, in a sufficiently densely filled
Tree, no node is more than $O(\log(n))$ away from the root.