Make costs of paths equal in a binary tree

Array Dynamic Programming Greedy Tree Binary Tree

58.3% acceptance

Feb 25, 2026

664

You are given an integer n representing the number of nodes in a perfect binary tree consisting of nodes numbered from 1 to n. The root of the tree is node 1 and each node i in the tree has two children where the left child is the node 2 * i and the right child is 2 * i + 1. Each node in the tree also has a cost represented by a given 0-indexed integer array cost of size n where cost[i] is the cost of node i + 1. You are allowed to increment the cost of any node by 1 any number of times. Return the minimum number of increments you need to make the cost of paths from the root to each leaf node equal.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_increments(n: i32, cost: Vec<i32>) -> i32 {
    let n = n as usize;
    let mut cost = cost;
    let mut ans = 0i32;
    // Process internal nodes from n/2 down to 1 (1-indexed)
    for i in (1..=(n / 2)).rev() {
      let left = 2 * i - 1;  // 0-indexed left child (1-indexed: 2i)
      let right = 2 * i;     // 0-indexed right child (1-indexed: 2i+1)
      ans += (cost[left] - cost[right]).abs();
      cost[i - 1] += cost[left].max(cost[right]);
    }
    ans
  }
}