The Tree

Nicolas Toulemont - December 23th 2022
Data Structures

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.

tree

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:

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:

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:

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:

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:

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