# Trees

## About

An absctract data type that represents a hierarchical tree structure with a set of connected nodes.

{% hint style="info" %}
Useful fo represent data in a non-linear form, making them suitable for representing hierarquical relationships.
{% endhint %}

Each node in the tree can be connected to **many** children nodes *(depending on the type of tree)*, but must be connected to exactly **one** parent node.

You may assume that in a Tree with `V` number of vertices (nodes), it will have $$E = V - 1$$ amount of `E` edges. *(Because each node will have at least 1 edge, connecting it to it's parent node)*

These constraints mean:

* There are no cycles or "loops". *(no node can be its own ancestor)*
* Each child can be treated like the root node of its own subtree. *(Making* `recursion` *a useful technique for tree traversal)*

## Terminology

| `node`   | The fundamental unit of the tree that holds data.                        |
| -------- | ------------------------------------------------------------------------ |
| `edge`   | The connection between two nodes.                                        |
| `root`   | The topmost node. *(Has depth 0)*                                        |
| `leaf`   | Node without children.                                                   |
| `height` | The longest path from the root to the deepest leaf.                      |
| `degree` | For a given node, its the number of children. *(A leaf has degree of 0)* |
| `depth`  | The number of edges from the root to the node.                           |
| `level`  | The same as depth, but it starts the count from 1, instead of 0.         |

## Traversing Trees

There are 3 types of tree traversals. *(That depends on when you do the visiting of the node)*

* **Pre-Order** traversal. *(Visit the node, then go Left, then go Right)*
* **In-Order** traversal. *(Go Left, then visit the node, then go Right)*
* **Post-Order** traversal. *(Go Left, then go Right, then visit the node)*

## Tree Types

| Type                     | Desciption                                                                                                                                                                                          |
| ------------------------ | --------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
| General Trees            | Trees where a node may have any amount of children.                                                                                                                                                 |
| Binary Trees             | A tree type in which **each node has at most two children**. *(It may have 0, 1 or 2)*                                                                                                              |
| Full Binary Trees        | A sub-type where every node has **either 0 or 2 children**.                                                                                                                                         |
| Complete Binary Trees    | <p>All levels, except possibly the last, are fully filled.</p><p>All nodes are as far left as possible.</p>                                                                                         |
| Perfect Binary Trees     | <p>All internal nodes have two children.</p><p>All leaves are at the same level.</p>                                                                                                                |
| Binary Search Tree (BST) | <p>A Binary Tree in which:</p><ul><li>The left child contains values smaller than the parent.</li><li>The right child contains values greater than the parent.</li></ul>                            |
| Balanced BST             | A Binary Tree where the height difference between the left and right subtrees of every node is at most 1.                                                                                           |
| AVL Tree                 | A self-balancing `Binary Search Tree` where the height of the left and right subtrees differ by at most 1.                                                                                          |
| Red-Black Tree           | It is a self-balancing `Binary Search Tree` with specific coloring rules to maintain balance.                                                                                                       |
| Trie                     | <p>A <code>General Tree</code> specifically used for efficient retrieval of strings, commonly used in autocomplete features.</p><p>Each node can have any number of children.</p>                   |
| B Trees                  | <p>Self-balancing Search Trees.</p><p>B-Trees can have <code>N</code> children.</p>                                                                                                                 |
| B+ Trees                 | Self-balancing Search Trees designed for filesystems and database systems.                                                                                                                          |
| Heap                     | <p>It is a <code>Binary Tree</code> where every child is:</p><ul><li>Smaller than the current node. (<code>Max Heap</code>)</li><li>Larger than the current node. (<code>Min Heap</code>)</li></ul> |