Skip to content
Hello Python

Expand One Tree Level

Practice ExerciseInterviewEasyBreadth-first Search

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement tree_level_sums(values, children, root). values[i] is a node value and children[i] lists child indices in a tree. Return one sum per breadth-first level starting at root. Return an empty list when root is -1.

Starter code

def tree_level_sums(values, children, root):
    pass
Test cases

three-level-tree

{
  "args": [
    [
      5,
      2,
      7,
      1,
      3
    ],
    [
      [
        1,
        2
      ],
      [
        3,
        4
      ],
      [],
      [],
      []
    ],
    0
  ]
}

Expected: [5,9,4]

single-node

{
  "args": [
    [
      8
    ],
    [
      []
    ],
    0
  ]
}

Expected: [8]

Wizard outline
  1. Step 1: Guard the empty tree

    Return an empty list before creating a queue when root is -1. The sentinel cannot be enqueued safely because -1 is a valid Python negative index.

  2. Step 2: Sum the root level

    Create a deque containing root and consume that one-node frontier into the first sum. A single-node tree isolates queue ownership and output shape from child expansion.

  3. Step 3: Freeze each frontier width

    Consume exactly len(queue) nodes per level, enqueue their children, and append one sum per frontier. Freezing the width prevents newly enqueued children from leaking into their parent level.

Footguns and prerequisites
  • Iterating until the queue is empty inside one level also consumes newly appended children and merges levels.
  • Using list.pop(0) works functionally but introduces repeated linear shifts.
  • trees and graphs
Reviewed references
Prepared Interview Problems
  • Binary Tree Level Order(opens in a new tab)

    Expand One Tree Level isolates at the start of each outer iteration, the queue contains exactly the current level in left-to-right order. That focused state discipline is required when implementing binary tree level order as a complete Interview Problem.

  • Binary Tree Right Side View(opens in a new tab)

    Expand One Tree Level isolates at the start of each outer iteration, the queue contains exactly the current level in left-to-right order. That focused state discipline is required when implementing binary tree right side view as a complete Interview Problem.

  • Bottom-Up Level Order Traversal(opens in a new tab)

    Expand One Tree Level isolates at the start of each outer iteration, the queue contains exactly the current level in left-to-right order. That focused state discipline is required when implementing bottom up level order as a complete Interview Problem.

  • Zigzag Level Order Traversal(opens in a new tab)

    Expand One Tree Level isolates at the start of each outer iteration, the queue contains exactly the current level in left-to-right order. That focused state discipline is required when implementing zigzag level order as a complete Interview Problem.

Recommended approach and implementation

Level-oriented tree output needs a queue plus the number of nodes present before the next frontier is appended. At the start of each outer iteration, the queue contains exactly the current level in left-to-right order.

Why it works: Capturing the current queue length isolates one level before children are appended. Summing exactly those nodes and enqueueing their children constructs the next level, so one correct sum is emitted per depth.

from collections import deque

def tree_level_sums(values, children, root):
    if root == -1:
        return []
    queue = deque([root])
    sums = []
    while queue:
        level_sum = 0
        for _ in range(len(queue)):
            node = queue.popleft()
            level_sum += values[node]
            queue.extend(children[node])
        sums.append(level_sum)
    return sums