Skip to content
Hello Python

Carry State Through Tree DFS

Practice ExerciseInterviewEasyDepth-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 root_to_leaf_sums(values, children, root). values[i] is a node value and children[i] lists child indices in a tree. Return root-to-leaf path sums in depth-first child order. Return an empty list when root is -1.

Starter code

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

branching-tree

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

Expected: [8,12]

single-node

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

Expected: [4]

Wizard outline
  1. Step 1: Guard the empty root

    Return no root-to-leaf sums when root is -1. The empty sentinel must be handled before recursion indexes values or children.

  2. Step 2: Record one leaf total

    Add the root value to a running total and append it when the root has no children. The leaf base case defines exactly when a path becomes a completed output.

  3. Step 3: Recurse into every child

    Call visit for each child with the accumulated total so every leaf path is recorded independently. Integers are immutable, so passing total downward preserves sibling isolation without manual undo logic.

Footguns and prerequisites
  • Appending a sum at every node reports partial paths instead of root-to-leaf paths.
  • Sharing one mutable total across sibling recursion leaks state from an earlier branch.
  • trees and graphs
Reviewed references
Prepared Interview Problems
  • Count Good Nodes in a Binary Tree(opens in a new tab)

    Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing count good tree nodes as a complete Interview Problem.

  • Kth Smallest in a BST(opens in a new tab)

    Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing kth smallest bst as a complete Interview Problem.

  • Lowest Common Ancestor in a BST(opens in a new tab)

    Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing lowest common ancestor bst as a complete Interview Problem.

  • Path Sum II(opens in a new tab)

    Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing path sum two as a complete Interview Problem.

  • Validate a Binary Search Tree(opens in a new tab)

    Carry State Through Tree DFS isolates the running total passed to a node equals the sum from the root through that node, independent of sibling branches. That focused state discipline is required when implementing validate binary search tree as a complete Interview Problem.

Recommended approach and implementation

Depth-first traversal can carry one immutable scalar state down each branch and record it only at terminal nodes. The running total passed to a node equals the sum from the root through that node, independent of sibling branches.

Why it works: Adding the current node to its parent total establishes the path sum for that node. Passing the resulting value by argument gives each child the correct prefix while sibling calls cannot mutate one another.

def root_to_leaf_sums(values, children, root):
    if root == -1:
        return []
    sums = []
    def visit(node, total):
        total += values[node]
        if not children[node]:
            sums.append(total)
            return
        for child in children[node]:
            visit(child, total)
    visit(root, 0)
    return sums