Reading the Org Chart

TIP103 Unit 11 Session 1 (Click for link to problem statements)

Reading the Org Chart

A company org chart is stored as a binary tree where each node is an employee. Leadership wants to read it out one management layer at a time, top to bottom, left to right.

Given the root of the tree, return a list of lists where each inner list holds the values on one level.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order(root):
    pass

Problem Highlights

💡 Difficulty: Medium
⏰ Time to complete: 20-25 mins
🛠️ Topics: Binary Trees, Breadth-First Search (BFS), Queues, Level Order Traversal

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

Established a set (2-3) of test cases to verify their own solution later.

Established a set (1-2) of edge cases to verify their solution handles complexities.

Have fully understood the problem and have no clarifying questions.

Have you verified any Time/Space Constraints for this problem?

Q: What does "one management layer at a time" mean in tree terms?
- A: It means grouping nodes by depth: the root is the first level, its children are the second level, and so on. Within each level we read left to right.
Q: What should the function return if the org chart is empty (root is None)?
- A: An empty list [], since there are no levels to report.
Q: Does every node have exactly two reports?
- A: No. Any node can have zero, one, or two children, so levels can be "ragged" — a missing child simply contributes nothing to the next level.

HAPPY CASE
Input:
        3
       / \
      9  20
        /  \
       15   7
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
Output: [[3], [9, 20], [15, 7]]
Explanation: The CEO (3) is the first layer, their two reports (9 and 20) are the second layer, and 20's two reports (15 and 7) are the third layer.

EDGE CASE
Input: root = None
Output: []
Explanation: An empty org chart has no levels to read out.

Input: root = TreeNode(1, TreeNode(2, TreeNode(3)))  (a left-skewed chain 1 -> 2 -> 3)
Output: [[1], [2], [3]]
Explanation: Each employee has a single report, so every management layer holds exactly one value.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Binary Tree Traversal Problems, we can consider the following approaches:

BFS (Breadth-First Search): Visiting nodes level by level is exactly what BFS with a queue does, making it the natural fit for level order traversal.
DFS (Depth-First Search) with level tracking: A recursive DFS that passes the current depth can also bucket values into per-level lists, but BFS matches the "layer at a time" framing more directly.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Use a queue to perform BFS. At the start of each round, the queue holds exactly one management layer. Record how many nodes are in that layer, pop exactly that many, collect their values into one inner list, and enqueue their children — which form the next layer. Repeat until the queue is empty.

1) If the root is None, return an empty list.
2) Initialize `levels` as an empty result list and a queue containing just the root.
3) While the queue is not empty:
   a) Let `level_size` be the current length of the queue (the number of nodes on this level).
   b) Pop `level_size` nodes from the front of the queue, appending each value to a `current_level` list.
   c) For each popped node, enqueue its left child then its right child, if they exist.
   d) Append `current_level` to `levels`.
4) Return `levels`.

⚠️ Common Mistakes

Popping from the queue until it is empty instead of snapshotting level_size first, which merges all levels into one list.
Using list.pop(0) instead of a deque, turning each dequeue into an O(N) operation.
Forgetting to handle a None root, causing the queue to start with None and crash on node.val.
Enqueuing None children and appending None values into the output.

4: I-mplement

Implement the code to solve the algorithm.

from collections import deque

def level_order(root):
    if not root:
        return []

    levels = []
    queue = deque([root])

    while queue:
        level_size = len(queue)  # Number of nodes on the current level
        current_level = []
        for _ in range(level_size):
            node = queue.popleft()
            current_level.append(node.val)
            # Children of this level form the next level
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
        levels.append(current_level)

    return levels

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

Input: root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
- Round 1: queue = [3], level_size = 1. Pop 3, enqueue 9 and 20. levels = 3.
- Round 2: queue = [9, 20], level_size = 2. Pop 9 (no children), pop 20, enqueue 15 and 7. levels = 3], [9, 20.
- Round 3: queue = [15, 7], level_size = 2. Pop both; neither has children. levels = 3], [9, 20], [15, 7.
- Queue is empty, so the loop ends.
- Output: [[3], [9, 20], [15, 7]]
Input: root = None
- The guard clause returns immediately.
- Output: []

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N is the number of nodes (employees) in the tree.

Time Complexity: O(N) because each node is enqueued and dequeued exactly once.
Space Complexity: O(N) for the output list of all values, and the queue itself holds up to one full level at a time — O(N/2) = O(N) nodes for the widest level of a bushy tree.

Uh oh!

Reading the Org Chart