PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep
|Home/Coding & Algorithms/Reinforce Labs

Compute minimum added stones to balance a tree

Last updated: Mar 29, 2026

Quick Overview

This question evaluates competency in tree algorithms, subtree aggregation, and integer resource balancing by requiring reasoning about hierarchical subtree sums and minimal additive adjustments.

  • medium
  • Reinforce Labs
  • Coding & Algorithms
  • Software Engineer

Compute minimum added stones to balance a tree

Company: Reinforce Labs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

You are given a **rooted tree** with `n` nodes labeled `1..n` (root is node `1`). Each node `i` initially contains `stones[i]` stones. Define the **subtree sum** of a node as the total number of stones in that node’s subtree (including itself). A node is considered **balanced** if **all of its children’s subtree sums are equal**. (Leaves are automatically balanced.) You are allowed to perform the following operation any number of times: - Choose any node and **add 1 stone** to it. **Task:** Return the **minimum number of stones you must add** so that **every node in the tree is balanced**. #### Input - `n` — number of nodes - `edges` — `n-1` undirected edges describing the tree - `stones[1..n]` — initial stone counts (non-negative integers) #### Output - An integer: the minimum total number of added stones. #### Constraints (typical) - `1 ≤ n ≤ 2e5` - `0 ≤ stones[i] ≤ 1e9` (You should aim for an `O(n)` or `O(n log n)` solution.)

Quick Answer: This question evaluates competency in tree algorithms, subtree aggregation, and integer resource balancing by requiring reasoning about hierarchical subtree sums and minimal additive adjustments.

Reinforce Labs logo
Reinforce Labs
Jan 8, 2026, 12:00 AM
Software Engineer
Take-home Project
Coding & Algorithms
1
0
Loading...

You are given a rooted tree with n nodes labeled 1..n (root is node 1). Each node i initially contains stones[i] stones.

Define the subtree sum of a node as the total number of stones in that node’s subtree (including itself).

A node is considered balanced if all of its children’s subtree sums are equal. (Leaves are automatically balanced.)

You are allowed to perform the following operation any number of times:

  • Choose any node and add 1 stone to it.

Task: Return the minimum number of stones you must add so that every node in the tree is balanced.

Input

  • n — number of nodes
  • edges — n-1 undirected edges describing the tree
  • stones[1..n] — initial stone counts (non-negative integers)

Output

  • An integer: the minimum total number of added stones.

Constraints (typical)

  • 1 ≤ n ≤ 2e5
  • 0 ≤ stones[i] ≤ 1e9

(You should aim for an O(n) or O(n log n) solution.)

Submit Your Answer to Earn 20XP

Sign in to leave a comment

Loading comments...

Browse More Questions

More Coding & Algorithms•More Reinforce Labs•More Software Engineer•Reinforce Labs Software Engineer•Reinforce Labs Coding & Algorithms•Software Engineer Coding & Algorithms
PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.