# Trees

A general tree is a data structure where each node can have zero or more children. Each node has exactly one parent except for the root that has no parent.

```cpp
std::vector<TreeNode*> stack;
```

## Definition

A tree T is defined by a root r and a (possibly empty) list of subtrees $T^1, T^2, ..., T^n$ where $n \geq 0$. Each subtree is itself a general tree according to the same definition.

## Diagram

`TreeNode`

```text
                    |------------------|
                    |       Data       |
                    |  l1          l2  |
                    |------------------|
                    /                \
                   /                  \
        |--------------|           |----------------------------|
        |     Data     |           |            Data            |
        |  l1      l2  |           |   l1        l2          l3 |
        |--------------|           |----------------------------|
         /           \                /         /             \
        /           |--------|  |------|   |------|        |----------|
    |------|        |  Data  |  | Data |   | Data |        |   Data   |
    | Data |        |  l1    |  |------|   |------|        | l1    l2 |
    |------|        |--------|                             |----------|
                      /                                     /        \
                |------|                                   /          \
                | Data |                             |------|       |------|
                |------|                             | Data |       | Data |
                                                     |------|       |  l1  |
                                                                    |------|
                                                                       /
                                                                      /
                                                                |------|
                                                                | Data |
                                                                |------|
```

---

Trees are traversed starting at the root. Traversals are often recursive because of the recursive nature of trees. It is **bad** practice to expose a reference of any node externally. However, in this lab you have the following publicly exposed:

- `TreeNode* root`
- `void add Child()`
- `TreeNode* getRoot()`
- `TreeNode* findNode()`
- `collection(TreeNode*) getChildren()`

---

Python-like pseudocode for Level-Order Traversal:

```py
LOT(root):
  # q is a queue of TreeNode references
  q;
  while q is not empty:
    node = q.dequeue()
    visit node
    for each child of ode:
        q.enqueue(child)
```

```py
LOT_ReportLevels(root):
    # result is a list of lists of TreeNode references
    result;
    # q is a queue of TreeNode refs
    q;
    while q is not empty:
        # level is a list of TreeNode references
        level;
        # levelSize is q.size(?)
        # incomplete
```