# The Tree

## What is a Tree ?

A tree is a data structure that represents a hierarchical structure between a set of connected nodes. Each node in the tree can be connected to many children (depending on the type of tree), but must be connected to exactly one parent, except for the root node, which has no parent.

It can have multiple uses, one of the better knowns is binary trees which enable logarithmic search operations on the nodes of the tree.

In this post tho, we will focus on building a basic tree data structure, which allow us to explore how Javascript generators functions can help build custom iterators for tree-based data structures.

## How to build a Tree in Typescript

Let's start with the building blocks of our tree: the `Node`

and `Tree`

classes.

### The Tree and Node classes

Our `Node`

class will have two properties:

- A
`name`

to identify it `children`

to contain its child nodes.

Our `Tree`

class will, at first, only have a `root`

property that will be the top of our tree.

```
class Node {
name: string
children: Node[]
constructor({ name, children }: { name: string; children: Node[] }) {
this.name = name
this.children = children
}
}
class Tree {
root: Node | null
constructor() {
this.root = null
}
}
```

Later we will want to add so methods to our `Tree`

class to make it useful, probably I/O operations (`get`

, `set`

, `update`

, `remove`

).
To be able to perform these operations, a common operation is to traverse our tree from the root to the leaves.

### Tree traversal

To easily access all the nodes of our tree, we need a way to iterate over every node of the tree.
But since our tree is not a native Javascript array, we cannot use built-in iterators like `forEach`

, `for of`

, etc.
Let's handle this by building our custom iterator to handle our specific needs using a generator function.

```
export class Tree {
root: Node | null
constructor() {
this.root = null
}
*traverse(node = this.root): Iterable<Node> {
if (!node) return
yield node
if (node.children.length) {
for (const child of node.children) {
yield* this.traverse(child)
}
}
}
}
```

This generator function is pretty simple, it recursively iterates over every node of the tree, yielding * ("giving")* each one back
to the function caller, before moving to each node children until it has yielded every leaf of the tree.

### I/O methods

Now that we have a method that easily iterates over our tree, we can add some I/O methods.

#### Set method

To set a node to our tree, we have to 2 cases:

- The tree doesn't have a root node yet, in this case, there is no need to give the tree a node name to insert the new node into.
- The tree already has a root node, in this case, we need to provide an address for the node we need to insert, here will use the node name as an address to find where to insert it.

With these two use cases in mind, and using our `traverse`

function to iterate within our tree, our set function is fairly simple.

```
type IOResult = Node[] | null | undefined
export class Tree {
root: Node | null
constructor() {
this.root = null
}
// ...
set(newNode: Node, parentNodeName?: string): IOResult {
if (this.root === null) {
this.root = new Node(newNode)
return [this.root]
}
if (this.root && !parentNodeName) {
throw new Error("parentNodeName is required once the tree is initialized")
}
const inserted: Node[] = []
for (const node of this.traverse()) {
if (node.name === parentNodeName) {
node.children.push(newNode)
inserted.push(node)
}
}
return inserted.length > 0 ? inserted : undefined
}
}
```

#### Get method

To read a specific node from our tree, we will add a `get`

method.
Since our `traverse`

function handle the iteration, this one is fairly simple, with only three
possible results:

- There is no root node, meaning that the only possible result is
`null`

. - There are one or more nodes with the queries name (we don't restrict the node names to be unique).
Therefore the result will be an array of nodes
`Node[]`

. - There is no matching node, meaning the queried name is
`undefined`

.

```
type IOResult = Node[] | null | undefined
export class Tree {
root: Node | null
constructor() {
this.root = null
}
// ...
get(nodeName: string): IOResult {
if (this.root === null) return null
const results: Node[] = []
for (const node of this.traverse()) {
if (node.name === nodeName) {
results.push(node)
}
}
return results.length > 0 ? results : undefined
}
}
```

#### Update method

Let's now add an `update`

method. It will be very similar to the `set`

method, which
in a way is about updating an existing node to add a new child node to it.
To keep it simple, we will keep its signature to a `boolean`

result, but we could
have an array with the updated nodes instead if we wanted to.

```
type IOResult = Node[] | null | undefined
export class Tree {
root: Node | null
constructor() {
this.root = null
}
// ...
update(nodeName: string, updatedNode: Partial<Node>): IOResult {
if (this.root === null) return null
const updated: Node[] = []
for (const node of this.traverse()) {
if (node.name === nodeName) {
Object.assign(node, updatedNode)
updated.push(node)
}
}
return updated.length > 0 ? updated : undefined
}
}
```

#### Remove method

Finally, let's enable the tree users to remove nodes from the tree. This one has a caveat because to remove a node we need to do two things:

- Find it
- Lift its children nodes to its parent node to avoid removing more nodes than one.

To do this, we will iterate over our nodes to find the target node when reaching its parent node. We will then do the following:

- Hold a reference to the target node
- Remove it from its parent children node array
- Adds the target node children nodes to its parent children nodes array

```
type IOResult = Node[] | null | undefined
export class Tree {
root: Node | null
constructor() {
this.root = null
}
// ...
remove(nodeName: string): IOResult {
if (!this.root) return null
const removed: Node[] = []
for (const node of this.traverse()) {
const foundChildNode = node.children.find(({ name }) => name === nodeName)
if (foundChildNode) {
removed.push(foundChildNode)
node.children = node.children.filter(({ name }) => name !== nodeName)
node.children.push(...foundChildNode.children)
}
}
return removed.length > 0 ? removed : undefined
}
}
```

That's it for this basic tree!

To conclude, we can see that a generator function can be a very useful abstraction over a custom iteration process. It has allowed us to separate the iteration from the I/O itself and keep our code simple and clean.

## From the same category

#### The Hashtable

Data Structures2020-12-05

Typescript implementation of a basic hashtable with insert, get and remove methods.

#### The Linked list

Data Structures2020-05-31

Typescript implementation of a linked-list.

#### The Queue

Data Structures2020-05-24

Typescript implementation of a basic queue and of a priority queue.

#### The Stack

Data Structures2020-05-19

Typescript implementation of a stack.