# Who Works Under Whom? Trees

List everyone who works under a manager in a company of 10,000, without rereading every row for every person: why a list of rows and a name-to-manager dictionary fall short, and the structure that fixes them, the tree, with its words (root, parent, child, leaf, depth and height).

Apprentice · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Name the root, parents, children and leaves of a tree
- Work out a node's depth and a tree's height
- Choose a tree over a flat list of rows when a job asks about a whole branch, and tell which data is a tree

## Key takeaways

- Rows of (name, manager) answer "who is Hana's manager?", but "everyone under Ava" rereads every row for every person found: O(n²), 100 million checks at 10,000 staff.
- A tree starts from one root node, and every other node has exactly one parent; in code, each node holds its own value and a list of its children.
- A node with no children is a leaf, and a node with its children, their children and so on is a subtree.
- A node's depth is how many steps it is from the root; a tree's height is the depth of its deepest node.
- Listing everyone under a person visits only their subtree, so the work grows with the size of the team, not the company.

**Before this:** *Finding Maya's Coat Without a Ticket: Hash Tables* finds one row by its name in one step. It has nothing to say about a whole branch of people, such as everyone who works under a manager.

The bike company has grown. Ava still owns it, but there are now 10,000 staff across forty stores, and the staff app keeps one row per person: their name and their manager's name. HR wants a new screen. Tap a name, and it lists **everyone who works under that person**: their reports, their reports' reports, and so on all the way down. Tap Ava and you get all 9,999 others; tap a store manager and you get that store.

You'll meet this shape wherever something sits *inside* or *under* something else: folders inside folders, replies to replies, boxes inside boxes on a web page. To keep the pictures small, this lesson uses the company as it started, with nine people:

| Name | Manager |
|---|---|
| Ava | nobody |
| Ben, Chloe, Ivy | Ava |
| Dev, Emi | Ben |
| Farah, Gus | Chloe |
| Hana | Farah |

## What would you try?

**Read the rows.** To find who's under Chloe, read every row and pick out the ones whose manager is Chloe: Farah and Gus. But Hana works under Farah, so read every row again for Farah, then again for Gus, then again for Hana. Every person you find costs another full read. At 10,000 staff, tapping Ava reads 10,000 rows for each of 10,000 people: **100 million checks** for one tap. That's O(n²): double the staff, four times the work.

**Look managers up in a dictionary.** The hash table from Module 5 makes "who is Hana's manager?" one step: a dictionary from each name to their manager. To find everyone under Chloe, start from every person and climb: Hana's manager is Farah, Farah's is Chloe, so Hana is in. If the chart is 6 levels deep, that's up to 6 steps for each of the 10,000 people, about 60,000 steps, whether Chloe's team has 3 people or 3,000. In Big-O that's O(n·h), with h for the number of levels. And the names come out in a jumble, not team by team.

**Turn the dictionary around.** Make the key the manager and the value the list of their reports: Chloe → Farah, Gus; Farah → Hana. Now "everyone under Chloe" is: look up Chloe, then look up each of her reports, then each of theirs. Every lookup lands on real team members, so the work is the size of the team: 4 lookups for Chloe's 3 people, and about 10,000 for Ava's 9,999.

| What we tried | Everyone under Ava, at 10,000 staff | Where it breaks |
|---|---|---|
| Read the rows again for each person | 100 million checks, O(n²) | every tap rereads the company |
| Name → manager, climbing from everyone | about 60,000 steps, O(n·h) | a team of 3 costs as much as the company |
| Manager → their reports | about 10,000 lookups: the team's size | nothing, for this job |

## The questions that lead to it

**What does the screen do most?** It starts at one person and goes *down*: their reports, then their reports' reports. It never needs anyone outside that branch.

**What did the turned-around dictionary get right?** Each person led straight to the people under them.

So what if each person **carried their own list of reports**? Ava holds Ben, Chloe and Ivy; Chloe holds Farah and Gus; Farah holds Hana. Then the whole company hangs from one person. Who reports to no one? Ava. Start from her and you can reach every person by going down, and there's exactly one way down to each of them, because everyone has exactly one manager.

## How it got its name

This shape was so useful that it got a name: a **tree**. Drawn as a chart, it branches out from one person at the top: a tree upside down, with the root at the top and the branches growing downward. The folders on your computer make the same shape: one top folder, folders inside it, and files inside those.

![Two trees side by side. On the left, the bike company's org chart: Ava at the top labeled root; Ben, Chloe and Ivy under her; Dev and Emi under Ben; Farah and Gus under Chloe; Hana under Farah. Chloe is labeled parent of Farah and Gus, Farah is labeled a child of Chloe, and Dev, Emi, Hana, Gus and Ivy are labeled leaves. On the right, a folder tree with the same labels: a Documents folder as the root, School and Photos folders inside it, and files at the ends as leaves](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/498fe97b08fc4ba5afc98fe806af56a3.webp)

Each box in a tree is a **node**, and the words for how nodes connect come from a family tree:

- **Root:** the one node at the top, with nothing above it. Ava is the root.
- **Parent and child:** the node right above another is its **parent**, and the nodes right below a node are its **children**. Chloe is the parent of Farah and Gus; they are her children, the people who report to her.
- **Leaf:** a node with no children. Dev, Emi, Hana, Gus and Ivy are leaves: nobody reports to them.
- **Subtree:** a node with its children, their children and so on, all the way down. Chloe's subtree is Chloe, Farah, Gus and Hana: her whole workshop team, and exactly what the new screen lists.

Two rules make something a tree: exactly one root, and every other node has exactly one parent. Nobody reports to two managers, and no folder sits in two places at once.

## Depth and height

Two numbers describe where things sit in a tree:

- A node's **depth** is how many steps it is from the root. Ava's depth is 0, because she *is* the root. Ben, Chloe and Ivy are at depth 1; Dev, Emi, Farah and Gus at depth 2; Hana at depth 3.
- A tree's **height** is the depth of its deepest node: how far the longest branch reaches down. This chart has a height of 3, because Hana is 3 steps from Ava.

![The bike company's org chart in four horizontal bands, one per depth: depth 0 holds Ava, depth 1 holds Ben, Chloe and Ivy, depth 2 holds Dev, Emi, Farah and Gus, and depth 3 holds Hana. An arrow down the side from Ava to Hana reads "height 3: the longest path from the root"](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/36aeb0a38a734440b16ca77313c181f6.webp)

Height decides how much work it is to walk from the root down to a leaf: the h in the dictionary try above. A tall, thin chart makes the walk long; a short, wide one makes it quick. The next chapter is all about keeping trees short.

## A tree in code

A tree node is a small object that holds its own value and a list of its children. Here, an `Employee` holds a name and a list of reports. The program builds the bike company's chart, asks a few questions about it, lists everyone under Chloe the way the new screen will, and works out the chart's height.

```csharp
Employee ava = new Employee("Ava");
Employee ben = ava.Add(new Employee("Ben"));
Employee chloe = ava.Add(new Employee("Chloe"));
ava.Add(new Employee("Ivy"));
ben.Add(new Employee("Dev"));
ben.Add(new Employee("Emi"));
Employee farah = chloe.Add(new Employee("Farah"));
Employee gus = chloe.Add(new Employee("Gus"));
farah.Add(new Employee("Hana"));

Console.WriteLine("Root: " + ava.Name);
Console.WriteLine("Ava's reports: " + Names(ava.Reports));
Console.WriteLine("Chloe's reports: " + Names(chloe.Reports));
Console.WriteLine("Is Gus a leaf? " + (gus.Reports.Count == 0 ? "yes" : "no"));
Console.WriteLine("Is Farah a leaf? " + (farah.Reports.Count == 0 ? "yes" : "no"));
Console.WriteLine("Everyone under Chloe: " + string.Join(", ", Team(chloe)));
Console.WriteLine("Height of the chart: " + Height(ava));

string Names(List<Employee> people)
{
    List<string> names = new List<string>();
    foreach (Employee person in people)
    {
        names.Add(person.Name);
    }
    return string.Join(", ", names);
}

List<string> Team(Employee person)
{
    List<string> team = new List<string>();
    foreach (Employee report in person.Reports)
    {
        team.Add(report.Name);
        team.AddRange(Team(report));
    }
    return team;
}

int Height(Employee person)
{
    int tallest = 0;
    foreach (Employee report in person.Reports)
    {
        tallest = Math.Max(tallest, 1 + Height(report));
    }
    return tallest;
}

class Employee
{
    public string Name { get; }
    public List<Employee> Reports { get; } = new List<Employee>();

    public Employee(string name)
    {
        Name = name;
    }

    public Employee Add(Employee report)
    {
        Reports.Add(report);
        return report;
    }
}
```

```text
Root: Ava
Ava's reports: Ben, Chloe, Ivy
Chloe's reports: Farah, Gus
Is Gus a leaf? yes
Is Farah a leaf? no
Everyone under Chloe: Farah, Hana, Gus
Height of the chart: 3
```

```java
class Employee {
    String name;
    List<Employee> reports = new ArrayList<>();

    Employee(String name) {
        this.name = name;
    }

    Employee add(Employee report) {
        reports.add(report);
        return report;
    }
}

String names(List<Employee> people) {
    List<String> names = new ArrayList<>();
    for (Employee person : people) {
        names.add(person.name);
    }
    return String.join(", ", names);
}

List<String> team(Employee person) {
    List<String> names = new ArrayList<>();
    for (Employee report : person.reports) {
        names.add(report.name);
        names.addAll(team(report));
    }
    return names;
}

int height(Employee person) {
    int tallest = 0;
    for (Employee report : person.reports) {
        tallest = Math.max(tallest, 1 + height(report));
    }
    return tallest;
}

void main() {
    Employee ava = new Employee("Ava");
    Employee ben = ava.add(new Employee("Ben"));
    Employee chloe = ava.add(new Employee("Chloe"));
    ava.add(new Employee("Ivy"));
    ben.add(new Employee("Dev"));
    ben.add(new Employee("Emi"));
    Employee farah = chloe.add(new Employee("Farah"));
    Employee gus = chloe.add(new Employee("Gus"));
    farah.add(new Employee("Hana"));

    IO.println("Root: " + ava.name);
    IO.println("Ava's reports: " + names(ava.reports));
    IO.println("Chloe's reports: " + names(chloe.reports));
    IO.println("Is Gus a leaf? " + (gus.reports.isEmpty() ? "yes" : "no"));
    IO.println("Is Farah a leaf? " + (farah.reports.isEmpty() ? "yes" : "no"));
    IO.println("Everyone under Chloe: " + String.join(", ", team(chloe)));
    IO.println("Height of the chart: " + height(ava));
}
```

```text
Root: Ava
Ava's reports: Ben, Chloe, Ivy
Chloe's reports: Farah, Gus
Is Gus a leaf? yes
Is Farah a leaf? no
Everyone under Chloe: Farah, Hana, Gus
Height of the chart: 3
```

```python
class Employee:
    def __init__(self, name):
        self.name = name
        self.reports = []

    def add(self, report):
        self.reports.append(report)
        return report


def names(people):
    return ", ".join(person.name for person in people)


def team(person):
    names = []
    for report in person.reports:
        names.append(report.name)
        names.extend(team(report))
    return names


def height(person):
    tallest = 0
    for report in person.reports:
        tallest = max(tallest, 1 + height(report))
    return tallest


ava = Employee("Ava")
ben = ava.add(Employee("Ben"))
chloe = ava.add(Employee("Chloe"))
ava.add(Employee("Ivy"))
ben.add(Employee("Dev"))
ben.add(Employee("Emi"))
farah = chloe.add(Employee("Farah"))
gus = chloe.add(Employee("Gus"))
farah.add(Employee("Hana"))

print("Root: " + ava.name)
print("Ava's reports: " + names(ava.reports))
print("Chloe's reports: " + names(chloe.reports))
print("Is Gus a leaf? " + ("yes" if len(gus.reports) == 0 else "no"))
print("Is Farah a leaf? " + ("yes" if len(farah.reports) == 0 else "no"))
print("Everyone under Chloe: " + ", ".join(team(chloe)))
print(f"Height of the chart: {height(ava)}")
```

```text
Root: Ava
Ava's reports: Ben, Chloe, Ivy
Chloe's reports: Farah, Gus
Is Gus a leaf? yes
Is Farah a leaf? no
Everyone under Chloe: Farah, Hana, Gus
Height of the chart: 3
```

```javascript
class Employee {
  constructor(name) {
    this.name = name;
    this.reports = [];
  }

  add(report) {
    this.reports.push(report);
    return report;
  }
}

function names(people) {
  return people.map((person) => person.name).join(", ");
}

function team(person) {
  const names = [];
  for (const report of person.reports) {
    names.push(report.name);
    names.push(...team(report));
  }
  return names;
}

function height(person) {
  let tallest = 0;
  for (const report of person.reports) {
    tallest = Math.max(tallest, 1 + height(report));
  }
  return tallest;
}

const ava = new Employee("Ava");
const ben = ava.add(new Employee("Ben"));
const chloe = ava.add(new Employee("Chloe"));
ava.add(new Employee("Ivy"));
ben.add(new Employee("Dev"));
ben.add(new Employee("Emi"));
const farah = chloe.add(new Employee("Farah"));
const gus = chloe.add(new Employee("Gus"));
farah.add(new Employee("Hana"));

console.log(`Root: ${ava.name}`);
console.log(`Ava's reports: ${names(ava.reports)}`);
console.log(`Chloe's reports: ${names(chloe.reports)}`);
console.log(`Is Gus a leaf? ${gus.reports.length === 0 ? "yes" : "no"}`);
console.log(`Is Farah a leaf? ${farah.reports.length === 0 ? "yes" : "no"}`);
console.log(`Everyone under Chloe: ${team(chloe).join(", ")}`);
console.log(`Height of the chart: ${height(ava)}`);
```

```text
Root: Ava
Ava's reports: Ben, Chloe, Ivy
Chloe's reports: Farah, Gus
Is Gus a leaf? yes
Is Farah a leaf? no
Everyone under Chloe: Farah, Hana, Gus
Height of the chart: 3
```

```typescript
class Employee {
  name: string;
  reports: Employee[] = [];

  constructor(name: string) {
    this.name = name;
  }

  add(report: Employee): Employee {
    this.reports.push(report);
    return report;
  }
}

function names(people: Employee[]): string {
  return people.map((person) => person.name).join(", ");
}

function team(person: Employee): string[] {
  const names: string[] = [];
  for (const report of person.reports) {
    names.push(report.name);
    names.push(...team(report));
  }
  return names;
}

function height(person: Employee): number {
  let tallest = 0;
  for (const report of person.reports) {
    tallest = Math.max(tallest, 1 + height(report));
  }
  return tallest;
}

const ava = new Employee("Ava");
const ben = ava.add(new Employee("Ben"));
const chloe = ava.add(new Employee("Chloe"));
ava.add(new Employee("Ivy"));
ben.add(new Employee("Dev"));
ben.add(new Employee("Emi"));
const farah = chloe.add(new Employee("Farah"));
const gus = chloe.add(new Employee("Gus"));
farah.add(new Employee("Hana"));

console.log(`Root: ${ava.name}`);
console.log(`Ava's reports: ${names(ava.reports)}`);
console.log(`Chloe's reports: ${names(chloe.reports)}`);
console.log(`Is Gus a leaf? ${gus.reports.length === 0 ? "yes" : "no"}`);
console.log(`Is Farah a leaf? ${farah.reports.length === 0 ? "yes" : "no"}`);
console.log(`Everyone under Chloe: ${team(chloe).join(", ")}`);
console.log(`Height of the chart: ${height(ava)}`);
```

```text
Root: Ava
Ava's reports: Ben, Chloe, Ivy
Chloe's reports: Farah, Gus
Is Gus a leaf? yes
Is Farah a leaf? no
Everyone under Chloe: Farah, Hana, Gus
Height of the chart: 3
```

`Team` is the new screen: for each report, add their name, then everyone under them, which is the same question asked one level down, the way the *Recursion* module solves a big problem from smaller ones of the same shape. `Height` reads like the definition: a leaf has height 0, and anyone else is one step taller than their tallest report's subtree. `Add` hands back the new employee, so the program can keep a name for anyone it wants to add reports to later.

**Try it.** Give Hana an apprentice of her own: keep Hana in a variable when Farah adds her, the way the program keeps `farah`, then add an employee named Jo to Hana's reports. Run it again. Jo joins Chloe's team, the height becomes 4, and Hana is no longer a leaf.

## In your textbook

Some textbooks count a tree's height in **levels** instead of steps, so they'd call the bike company's chart height 4, and a single node height 1 rather than 0. Both describe the same tree; check which one your class uses before you answer a homework question.

## The tree's cost card

For a tree like this one, where the children are in no particular order:

| Operation | Big-O | Why, in everyday terms |
|---|---|---|
| Add a report under a manager you already have | O(1) | Put one more name on their list |
| List everyone under a person | O(size of their team) | Go down their branch only; nobody outside it is checked |
| Count everyone, or work out the height | O(n) | Each person is visited once |
| Find a person by name | O(n) | Nothing tells you which branch to take, so you may check everyone |

**The honest rival:** if the only question were "who is Hana's manager?", the name → manager dictionary would win, in one step. Real staff apps often keep both: the dictionary to find a person's node by name, and the tree to walk down from it. On its own, the tree finds a person in O(n). A tree that keeps its children in order, so a search knows which branch to take, comes next: *A Contact List That's Fast to Search and Easy to Change: Binary Search Trees*.

## Check yourself

2 questions to try on the lesson page.

## So what

When a question is about a whole branch (everyone under a manager, everything inside a folder, every reply under a comment), keep the data as a tree, and the work grows with the branch, not with everything you store. Every tree later in this module, from binary search trees to heaps, is built from the node you wrote here.

## Key terms

- [Tree](https://www.ask-codey.com/glossary/tree)
- [Root Node](https://www.ask-codey.com/glossary/root-node)
- [Leaf Node](https://www.ask-codey.com/glossary/leaf-node)
- [Subtree](https://www.ask-codey.com/glossary/subtree)
- [Node Depth](https://www.ask-codey.com/glossary/node-depth)
- [Tree Height](https://www.ask-codey.com/glossary/tree-height)

## Cheat sheets

- [Who Works Under Whom? Trees](https://www.ask-codey.com/cheat-sheets/ds-trees-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-trees
