Example of tree data structure

Tree structures are so common and this article walks you through how to write code that represents the tree structure

dreamstime.com

An example of where tree structure is used in real life is a company’s hierarchy. As you can see in the image above each person (employee) has a boss all the way up to the CEO of a company. The bigger the company the more complicated the tree structure is.

Each person represents a node. A node at the bottom is called a leaf. The node at the top is called the root.

The root node doesn’t have a parent, but it has two children. Each of these children has two children of their own- leaves. As we can see in the image above, however, each node- including the root- could have as many children. The leaf node, however, doesn’t have any children as it is the lowest in the hierarchy.

This is a diagram that represents the same company. In practice, we may need to calculate the:

1. number of employees in the company
2. total money the company is spending on salary
3. number of employees who work under a certain manager
4. total salary of employees under a certain manager or in certain team
5. number of people who make over a certain amount of money

In code, I am going to explain the last item in the list above. I will walk you over how we calculate the number of employees who make over a $100,000 , using JavaScript.

employeesThatMakeOver(amount) {
  let employees = [];
  if (this.salary > amount) {
    employees.push(this.name);
  }
  if (this.subordinates.length > 0) {
    for (const subordinate of this.subordinates) {
      const subordinatesThatMakesOver =                        subordinate.employeesThatMakeOver(amount);
      employees = employees.concat(subordinatesThatMakesOver);
    }
  }
  return employees;
}

The function can be called with employeesThatMakeOver(100,000)

What are we doing here?

We are starting at the root node Adam who is the CEO of this small, hypothetical company.

We are checking his salary. If it is over $100,000 , we added his name to the array of people making over$100,000 . Then we are moving to his subordinates, checking each one at a time.

For each subordinate, we are checking if their salary is over $100,000 adding their names to the array of people making over$100,000 . Then we are moving to their subordinates, checking each one at a time.

You can sense the repetition, as this is exactly what our function employeesThatMakeOver(amount) is doing, so instead of repeating the steps, we can simply call the function employeesThatMakeOver(amount) .

That is recursion. It is particularly powerful when we don’t know how large the tree is or how many times we need to repeat the steps.

If you are not familiar with recursion, you may check this article:

Dijkstra was right - recursion should not be difficult

What is the word this ?

this refers to the class Employee as you see below, and the function employeesThatMakeOver(amount) is part of the class

class Employee {
  constructor(name, title, salary) {
    this.name = name;
    this.title = title;
    this.salary = salary;
    this.boss = null;
    this.subordinates = [];
  }
  employeesThatMakeOver(amount) {...}
}

Here is a good article that exposes you to classes and this

Introduction to JavaScript: Classes

This Employee class is used to create as many Employee objects as a company needs i.e for every manager in the company. Each manager would have a boss and subordinates. The example above shows that the Employee has no boss, this.boss = null; that is the case for the CEO or therootnode since it has no parent.

The example we walked through above follows a depth-first search technique.

But what is a depth-first search?

In a depth-first search, we try to get to the leaf nodes. In our example when checking for employeesThatMakeOver $100,000 , we first check Adam then Omer , then both Sarah and Andy . After that, we check Anton then Ali and John .

There is also a breadth-first search

In a breadth-first search, we visit the top nodes first before we move to the lower levels. In the same example, when checking for employeesThatMakeOver $100,000 , we first check Adam then Anton and Omer, then we move down to their children starting with Ali , John , Sarah then Andy .