Print the Chart, Count the Teams: Walking a Tree in the Right Order

Show one org chart three ways (printed with each team indented, with each manager's head count, and one level at a time) by visiting every person in the order each job needs: the four traversals, and which job each one is for.

Journeyman · Data Structures · Updated

By

After this lesson you can

  • Give the visiting order of a pre-order, post-order, level-order or in-order traversal
  • Choose the traversal that fits a job, such as printing a chart or adding up sizes

Key takeaways

  • A traversal visits every node of a tree once, in a planned order. Every traversal is O(n).
  • Pre-order visits a node before its children; post-order visits it after them.
  • Level-order visits the tree one depth at a time, using a queue.
  • In-order is for binary trees: left child, then the node, then the right child. In a binary search tree it gives sorted order.
  • The job picks the walk: a parent's line before its team's lines is pre-order, a total that needs its parts first is post-order, and nearest first is level-order.

Before this: Who Works Under Whom? Trees lists one team by going down its branch. Showing the whole chart, in an order a screen can use, needs a plan for which branch to visit first.

The staff app's org chart page needs the bike company's chart three ways, all from the same tree:

  1. The chart, printed: every person on their own line, each team indented under its manager.
  2. Head counts: each manager with the size of their whole team beside their name, such as "Chloe (3)".
  3. By level: Ava, then everyone one step below her, then everyone two steps below, for a panel that shows who's closest to the top.

Every view visits all nine people. What changes is the order, and the wrong order makes a view impossible to build.

What would you try?

Loop over the stored people. Keep everyone in a list, in the order they were added, and print it. The list is flat: nothing in it says Hana belongs under Farah, so there's no way to indent her. A list has one order, and it isn't the chart's.

Rescan for each level. For the by-level view, walk the whole tree once picking out everyone at depth 0, again for depth 1, again for depth 2, and so on. It works, but each level costs a walk of the whole company: 10,000 staff in 6 levels is 60,000 visits for one screen, O(n·h), and a taller chart costs more.

Print a person, then their team. For the printed chart, write a person's line, then do the same for each of their reports with two more spaces in front. It works: Ava, then Ben's team, then Chloe's, then Ivy. Now try the same order for head counts. When you reach Chloe, her line has to say "Chloe (3)", but you haven't counted Farah, Hana or Gus yet. In this order, the count always comes too late.

What we tried Printed chart Head counts By level
Loop over the stored list no nesting to indent no teams to count no levels
Rescan for each level not its job not its job works, but O(n·h)
A person, then their team works the count comes too late not its job

The questions that lead to it

Can a manager's line be printed before their team's? It has to be: the manager's line sits on top. So visit a person before their reports.

Can you know Chloe's head count before you've counted Farah's team? No. A total needs its parts first. So visit everyone under a person before the person, and add their counts up on the way back.

To finish a whole level before going deeper, how do you remember who's waiting? Everyone found on one level has to wait until that level is done, in the order they were found. That's a first-in, first-out line: the queue from Module 2.

So the same tree is visited in three different orders, one per job. Each one has a name.

Four ways to walk a tree

A walk that visits every node of a tree once is called a traversal. Here is the bike company's chart again, with Ava at the root. The four traversals below visit the same nine people; only the order changes.

Four small trees in a two by two grid, each with its nodes numbered in visiting order. Pre-order on the org chart: Ava 1, Ben 2, Dev 3, Emi 4, Chloe 5, Farah 6, Hana 7, Gus 8, Ivy 9. Post-order on the org chart: Dev 1, Emi 2, Ben 3, Hana 4, Farah 5, Gus 6, Chloe 7, Ivy 8, Ava 9. Level-order on the org chart: Ava 1, then Ben, Chloe and Ivy 2 to 4, then Dev, Emi, Farah and Gus 5 to 8, then Hana 9. In-order on a binary tree of contacts: Ana 1, Diego 2, Kai 3, Maya 4, Rosa 5, Tom 6, Zoe 7, which is alphabetical order

  • Pre-order: the node first, then its children. Ava, then Ben's whole team, then Chloe's, then Ivy: Ava, Ben, Dev, Emi, Chloe, Farah, Hana, Gus, Ivy. It's the printed chart's order, and the way a book's table of contents reads: a chapter's title, then its sections.
  • Post-order: the children first, then the node. Nobody is visited until everyone under them has been: Dev, Emi, Ben, Hana, Farah, Gus, Chloe, Ivy, Ava. It's the head counts' order. The root always comes last.
  • Level-order: one depth at a time. Ava, then everyone at depth 1, then everyone at depth 2: Ava, Ben, Chloe, Ivy, Dev, Emi, Farah, Gus, Hana. It's how you'd tour a building floor by floor.
  • In-order: left child, then the node, then the right child. This one is only for binary trees, where every node has at most two children, a left one and a right one. In the next chapter's binary search trees, in-order visits the values in sorted order.

The "pre" and "post" say when the node itself is visited: before its children or after them.

Pre-order and post-order in code

Both are a few lines of recursion. The only difference is where the node's own name goes: before the loop over its children, or after it. This time the chart is built in one go: each Employee is made with its reports inside it, so the code's indentation looks like the chart.

Employee ava = new Employee("Ava",
    new Employee("Ben",
        new Employee("Dev"),
        new Employee("Emi")),
    new Employee("Chloe",
        new Employee("Farah",
            new Employee("Hana")),
        new Employee("Gus")),
    new Employee("Ivy"));

List<string> preOrder = new List<string>();
PreOrder(ava, preOrder);
Console.WriteLine("Pre-order: " + string.Join(", ", preOrder));

List<string> postOrder = new List<string>();
PostOrder(ava, postOrder);
Console.WriteLine("Post-order: " + string.Join(", ", postOrder));

void PreOrder(Employee person, List<string> visited)
{
    visited.Add(person.Name);
    foreach (Employee report in person.Reports)
    {
        PreOrder(report, visited);
    }
}

void PostOrder(Employee person, List<string> visited)
{
    foreach (Employee report in person.Reports)
    {
        PostOrder(report, visited);
    }
    visited.Add(person.Name);
}

class Employee
{
    public string Name { get; }
    public List<Employee> Reports { get; }

    public Employee(string name, params Employee[] reports)
    {
        Name = name;
        Reports = new List<Employee>(reports);
    }
}
Pre-order: Ava, Ben, Dev, Emi, Chloe, Farah, Hana, Gus, Ivy
Post-order: Dev, Emi, Ben, Hana, Farah, Gus, Chloe, Ivy, Ava
class Employee {
    String name;
    List<Employee> reports;

    Employee(String name, Employee... reports) {
        this.name = name;
        this.reports = List.of(reports);
    }
}

void preOrder(Employee person, List<String> visited) {
    visited.add(person.name);
    for (Employee report : person.reports) {
        preOrder(report, visited);
    }
}

void postOrder(Employee person, List<String> visited) {
    for (Employee report : person.reports) {
        postOrder(report, visited);
    }
    visited.add(person.name);
}

void main() {
    Employee ava = new Employee("Ava",
        new Employee("Ben",
            new Employee("Dev"),
            new Employee("Emi")),
        new Employee("Chloe",
            new Employee("Farah",
                new Employee("Hana")),
            new Employee("Gus")),
        new Employee("Ivy"));

    List<String> pre = new ArrayList<>();
    preOrder(ava, pre);
    IO.println("Pre-order: " + String.join(", ", pre));

    List<String> post = new ArrayList<>();
    postOrder(ava, post);
    IO.println("Post-order: " + String.join(", ", post));
}
Pre-order: Ava, Ben, Dev, Emi, Chloe, Farah, Hana, Gus, Ivy
Post-order: Dev, Emi, Ben, Hana, Farah, Gus, Chloe, Ivy, Ava
class Employee:
    def __init__(self, name, *reports):
        self.name = name
        self.reports = list(reports)


def pre_order(person, visited):
    visited.append(person.name)
    for report in person.reports:
        pre_order(report, visited)


def post_order(person, visited):
    for report in person.reports:
        post_order(report, visited)
    visited.append(person.name)


ava = Employee("Ava",
    Employee("Ben",
        Employee("Dev"),
        Employee("Emi")),
    Employee("Chloe",
        Employee("Farah",
            Employee("Hana")),
        Employee("Gus")),
    Employee("Ivy"))

pre = []
pre_order(ava, pre)
print("Pre-order: " + ", ".join(pre))

post = []
post_order(ava, post)
print("Post-order: " + ", ".join(post))
Pre-order: Ava, Ben, Dev, Emi, Chloe, Farah, Hana, Gus, Ivy
Post-order: Dev, Emi, Ben, Hana, Farah, Gus, Chloe, Ivy, Ava
class Employee {
  constructor(name, ...reports) {
    this.name = name;
    this.reports = reports;
  }
}

function preOrder(person, visited) {
  visited.push(person.name);
  for (const report of person.reports) {
    preOrder(report, visited);
  }
}

function postOrder(person, visited) {
  for (const report of person.reports) {
    postOrder(report, visited);
  }
  visited.push(person.name);
}

const ava = new Employee("Ava",
  new Employee("Ben",
    new Employee("Dev"),
    new Employee("Emi")),
  new Employee("Chloe",
    new Employee("Farah",
      new Employee("Hana")),
    new Employee("Gus")),
  new Employee("Ivy"));

const pre = [];
preOrder(ava, pre);
console.log(`Pre-order: ${pre.join(", ")}`);

const post = [];
postOrder(ava, post);
console.log(`Post-order: ${post.join(", ")}`);
Pre-order: Ava, Ben, Dev, Emi, Chloe, Farah, Hana, Gus, Ivy
Post-order: Dev, Emi, Ben, Hana, Farah, Gus, Chloe, Ivy, Ava
class Employee {
  name: string;
  reports: Employee[];

  constructor(name: string, ...reports: Employee[]) {
    this.name = name;
    this.reports = reports;
  }
}

function preOrder(person: Employee, visited: string[]): void {
  visited.push(person.name);
  for (const report of person.reports) {
    preOrder(report, visited);
  }
}

function postOrder(person: Employee, visited: string[]): void {
  for (const report of person.reports) {
    postOrder(report, visited);
  }
  visited.push(person.name);
}

const ava = new Employee("Ava",
  new Employee("Ben",
    new Employee("Dev"),
    new Employee("Emi")),
  new Employee("Chloe",
    new Employee("Farah",
      new Employee("Hana")),
    new Employee("Gus")),
  new Employee("Ivy"));

const pre: string[] = [];
preOrder(ava, pre);
console.log(`Pre-order: ${pre.join(", ")}`);

const post: string[] = [];
postOrder(ava, post);
console.log(`Post-order: ${post.join(", ")}`);
Pre-order: Ava, Ben, Dev, Emi, Chloe, Farah, Hana, Gus, Ivy
Post-order: Dev, Emi, Ben, Hana, Farah, Gus, Chloe, Ivy, Ava

Move one line, and the whole order changes: the printed chart's order becomes the head counts' order. Both walks go as deep as they can down one branch before trying the next, which is why textbooks call them depth-first.

Level-order in code: a queue

Level-order can't follow one branch down, because it has to finish a whole depth before going deeper. So it keeps a queue of people waiting to be visited, the first-in, first-out line from Module 2. Take the person at the front, visit them, and put their reports at the back. Everyone at depth 1 joins the line before anyone at depth 2, so the levels come out in order. To print one line per level, the loop counts how many people are in the queue when a level starts, and visits exactly that many.

Employee ava = new Employee("Ava",
    new Employee("Ben",
        new Employee("Dev"),
        new Employee("Emi")),
    new Employee("Chloe",
        new Employee("Farah",
            new Employee("Hana")),
        new Employee("Gus")),
    new Employee("Ivy"));

Queue<Employee> waiting = new Queue<Employee>();
waiting.Enqueue(ava);
int level = 0;
while (waiting.Count > 0)
{
    int onThisLevel = waiting.Count;
    List<string> names = new List<string>();
    for (int i = 0; i < onThisLevel; i++)
    {
        Employee person = waiting.Dequeue();
        names.Add(person.Name);
        foreach (Employee report in person.Reports)
        {
            waiting.Enqueue(report);
        }
    }
    Console.WriteLine("Level " + level + ": " + string.Join(", ", names));
    level++;
}

class Employee
{
    public string Name { get; }
    public List<Employee> Reports { get; }

    public Employee(string name, params Employee[] reports)
    {
        Name = name;
        Reports = new List<Employee>(reports);
    }
}
Level 0: Ava
Level 1: Ben, Chloe, Ivy
Level 2: Dev, Emi, Farah, Gus
Level 3: Hana
class Employee {
    String name;
    List<Employee> reports;

    Employee(String name, Employee... reports) {
        this.name = name;
        this.reports = List.of(reports);
    }
}

void main() {
    Employee ava = new Employee("Ava",
        new Employee("Ben",
            new Employee("Dev"),
            new Employee("Emi")),
        new Employee("Chloe",
            new Employee("Farah",
                new Employee("Hana")),
            new Employee("Gus")),
        new Employee("Ivy"));

    Deque<Employee> waiting = new ArrayDeque<>();
    waiting.add(ava);
    int level = 0;
    while (!waiting.isEmpty()) {
        int onThisLevel = waiting.size();
        List<String> names = new ArrayList<>();
        for (int i = 0; i < onThisLevel; i++) {
            Employee person = waiting.poll();
            names.add(person.name);
            waiting.addAll(person.reports);
        }
        IO.println("Level " + level + ": " + String.join(", ", names));
        level++;
    }
}
Level 0: Ava
Level 1: Ben, Chloe, Ivy
Level 2: Dev, Emi, Farah, Gus
Level 3: Hana
from collections import deque


class Employee:
    def __init__(self, name, *reports):
        self.name = name
        self.reports = list(reports)


ava = Employee("Ava",
    Employee("Ben",
        Employee("Dev"),
        Employee("Emi")),
    Employee("Chloe",
        Employee("Farah",
            Employee("Hana")),
        Employee("Gus")),
    Employee("Ivy"))

waiting = deque([ava])
level = 0
while waiting:
    on_this_level = len(waiting)
    names = []
    for _ in range(on_this_level):
        person = waiting.popleft()
        names.append(person.name)
        waiting.extend(person.reports)
    print(f"Level {level}: " + ", ".join(names))
    level += 1
Level 0: Ava
Level 1: Ben, Chloe, Ivy
Level 2: Dev, Emi, Farah, Gus
Level 3: Hana
class Employee {
  constructor(name, ...reports) {
    this.name = name;
    this.reports = reports;
  }
}

const ava = new Employee("Ava",
  new Employee("Ben",
    new Employee("Dev"),
    new Employee("Emi")),
  new Employee("Chloe",
    new Employee("Farah",
      new Employee("Hana")),
    new Employee("Gus")),
  new Employee("Ivy"));

const waiting = [ava];
let front = 0;
let level = 0;
while (front < waiting.length) {
  const levelEnd = waiting.length;
  const names = [];
  while (front < levelEnd) {
    const person = waiting[front];
    front++;
    names.push(person.name);
    waiting.push(...person.reports);
  }
  console.log(`Level ${level}: ${names.join(", ")}`);
  level++;
}
Level 0: Ava
Level 1: Ben, Chloe, Ivy
Level 2: Dev, Emi, Farah, Gus
Level 3: Hana
class Employee {
  name: string;
  reports: Employee[];

  constructor(name: string, ...reports: Employee[]) {
    this.name = name;
    this.reports = reports;
  }
}

const ava = new Employee("Ava",
  new Employee("Ben",
    new Employee("Dev"),
    new Employee("Emi")),
  new Employee("Chloe",
    new Employee("Farah",
      new Employee("Hana")),
    new Employee("Gus")),
  new Employee("Ivy"));

const waiting: Employee[] = [ava];
let front = 0;
let level = 0;
while (front < waiting.length) {
  const levelEnd = waiting.length;
  const names: string[] = [];
  while (front < levelEnd) {
    const person = waiting[front];
    front++;
    names.push(person.name);
    waiting.push(...person.reports);
  }
  console.log(`Level ${level}: ${names.join(", ")}`);
  level++;
}
Level 0: Ava
Level 1: Ben, Chloe, Ivy
Level 2: Dev, Emi, Farah, Gus
Level 3: Hana

JavaScript and TypeScript have no built-in queue. Their version keeps everyone in an array and moves a front index forward instead of calling shift(), which would slide every remaining item down one place each time. Visiting a tree level by level is also called breadth-first, and in Module 7 the same queue finds the fewest steps between two places on a map.

Which walk for which job

The three views from the start of the lesson are the first, third and fifth rows. The order is what makes a traversal right for a job:

Job Traversal Why
Print an indented org chart or folder list Pre-order A manager's line has to come before their team's lines
Copy a folder tree Pre-order A folder has to exist before you can put files in it
Show each manager's head count, or add up a folder's size Post-order A total needs its parts first: every child's total is ready before the parent adds them up
Delete a folder Post-order A folder has to be empty before it can go
Show the chart level by level, or the nearest things first Level-order It finishes each depth before the next
List a binary search tree's values in sorted order In-order Everything smaller is on the left, everything bigger on the right

Try it. In the pre-order program, add a fourth employee to Ava's reports, Jo, between Chloe and Ivy. Before you run it, write down where Jo will appear in each order, then check.

The traversals' cost card

Traversal Time Extra memory Why, in everyday terms
Pre-order, post-order, in-order O(n) Up to the tree's height Everyone is visited once; the walk remembers only the path from the root to where it is
Level-order O(n) Up to the widest level Everyone is visited once; the line holds at most one level and part of the next

Every traversal is O(n): you can't visit everyone in less time than it takes to visit everyone. That's also why the queue beats rescanning once per level, which was O(n·h). What the walks differ in is order, and the little bit of memory each one keeps while it walks.

Check yourself

2 questions to try on the lesson page.

So what

When you need to visit everything in a tree, the question isn't "how?" but "in which order does the job need it?". A line on top of its team: parent first. A total from its parts: children first. Nearest first: level by level. Pick the one the job needs, and the code is a few lines.

Key terms

Cheat sheets