InterviewDB
Question
·
Los Angeles
Children Counting: Count Nodes at Each Level of a Tree
phone
Question Details
Round 1 Coding
Problem
Given a tree (not necessarily binary), where each node has an ID and a list of children,
return a list where the i-th element is the number of nodes at depth i (root is depth 0).
python
class TreeNode:
def __init__(self, node_id: int, children: list['TreeNode'] = None):
self.node_id = node_id
self.children = children or []
def count_per_level(root: TreeNode) -> list[int]:
...
Example
1
/ | \
2 3 4
/| |
5 6 7
count_per_level(root)
# Level 0: [1] -> 1
# Level 1: [2,3,4] -> 3
# Level 2: [5,6,7] -> 3
# -> [1, 3, 3]
Follow-ups
- How do you implement this iteratively using a queue versus recursively? What are the trade-offs?
- How would you extend this to return the sum of node values at each level?
- Given two trees, how do you find the deepest common level where both trees have the same node count?
- If the tree has millions of nodes, how do you process it level by level without running out of memory?
Full Details
Round 1 Coding
Problem
Given a tree (not necessarily binary), where each node has an ID and a list of children,
return a list where the i-th element is the number of nodes at depth i (root is depth 0).
python
class TreeNode:
def __init__(self, node_id: int, children: list['TreeNode'] = None):
self.node_id = node_id
self.children = children or []
def count_per_level(root: TreeNode) -> list[int]:
...
Example
1
/ | \
2 3 4
/| |
5 6 7
count_per_level(root)
# Level 0: [1] -> 1
# Level 1: [2,3,4] -> 3
# Level 2: [5,6,7] -> 3
# -> [1, 3, 3]
Follow-ups
- How do you implement this iteratively using a queue versus recursively? What are the trade-offs?
- How would you extend this to return the sum of node values at each level?
- Given two trees, how do you find the deepest common level where both trees have the same node count?
- If the tree has millions of nodes, how do you process it level by level without running out of memory?
Free preview. Unlock all Patreon questions →
About This Question
This is a reported interview question from a patreon interview during the phone round.
It covers the following topics: Coding, Queue, Phone, Onsite .
More Patreon Interview Questions
LeetCode
#243 Shortest Word Distance
InterviewDB
Patreon SWE Onsite - Cache Layer
InterviewDB
Patreon SWE Phone - CD Command
InterviewDB
Employee Reporting: Build an Org Chart Query System for Hierarchical Reporting Structures
InterviewDB
Frontend Coding: Implement a Draggable Kanban Board with Column Management