Count Nodes Equal to Average of Subtree

Medium
1956.

Count Nodes Equal to Average of Subtree

Count Nodes Equal to Average of Subtree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.

Given the root of a binary tree, return how many nodes have a value equal to the average of the values in their subtree.

A node's subtree is the node together with all of its descendants. The average of k values is their sum divided by k, rounded down to an integer.

Example 1

Input
root = [4,8,5,0,1,null,6]
Output
5
Explanation
4: (4+8+5+0+1+6) / 6 = 4. 5: (5+6) / 2 = 5. 0, 1 and 6 are leaves. 8: (8+0+1) / 3 = 3, not 8. Five nodes match.

Example 2

Input
root = [1]
Output
1
Explanation
A leaf always equals its own average.

Example 3

Input
root = [2,1,4]
Output
3
Explanation
The root's average is 7 / 3 = 2 (rounded down), and both leaves match too.

Constraints

  • 1 <= number of nodes <= 1000
  • 0 <= Node.val <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var averageOfSubtree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Nodes Equal to Average of Subtree — Problem & Solution

Count Nodes Equal to Average of Subtree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Count Nodes Equal to Average of Subtree is a medium coding problem on depth-first search and trees, asked in Amazon, Google and Meta interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google, Meta
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the root of a binary tree, return how many nodes have a value equal to the average of the values in their subtree.

A node's subtree is the node together with all of its descendants. The average of k values is their sum divided by k, rounded down to an integer.

Example 1

Input: root = [4,8,5,0,1,null,6]
Output: 5
Explanation: 4: (4+8+5+0+1+6) / 6 = 4. 5: (5+6) / 2 = 5. 0, 1 and 6 are leaves. 8: (8+0+1) / 3 = 3, not 8. Five nodes match.

Example 2

Input: root = [1]
Output: 1
Explanation: A leaf always equals its own average.

Example 3

Input: root = [2,1,4]
Output: 3
Explanation: The root's average is 7 / 3 = 2 (rounded down), and both leaves match too.

Constraints

  • 1 <= number of nodes <= 1000
  • 0 <= Node.val <= 1000

Hints for Count Nodes Equal to Average of Subtree

  1. Hint 1

    A subtree's average needs only two numbers: its sum and its size.

  2. Hint 2

    Both combine from the children: sum = left sum + right sum + value, size = left size + right size + 1.

  3. Hint 3

    Compute them in one post-order walk and compare sum / size (integer division) with the node's value as you go.

How to solve Count Nodes Equal to Average of Subtree

A post-order walk returns each subtree's sum and size, built from its children's; the node is counted when the integer average equals its value.

Approach

  1. walk(node) returns (sum, size); a null node returns (0, 0).
  2. For a node, combine its children's pairs into sum = ls + rs + val and size = lc + rc + 1.
  3. If sum / size (rounded down) equals val, increase the count.
  4. Return (sum, size); the count after walking the root is the answer.

Why it works

Each subtree is the disjoint union of the node and its two child subtrees, so the sums and sizes add up exactly. Every node is visited once, after its children, so its pair is ready when it is tested.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Recomputing each subtree's sum from scratch is O(n^2).
  • Round down: values are non-negative, so plain integer division does it.

Reference solution

Python

from typing import Optional

def averageOfSubtree(root: Optional[TreeNode]) -> int:
    count = 0

    def walk(node):
        nonlocal count
        if node is None:
            return 0, 0
        ls, lc = walk(node.left)
        rs, rc = walk(node.right)
        s = ls + rs + node.val
        c = lc + rc + 1
        if s // c == node.val:
            count += 1
        return s, c

    walk(root)
    return count

Java

public static int averageOfSubtree(TreeNode root) {
    int[] count = new int[1];
    avgWalk(root, count);
    return count[0];
}

// Returns {sum, size} of the subtree.
static int[] avgWalk(TreeNode node, int[] count) {
    if (node == null) return new int[] {0, 0};
    int[] l = avgWalk(node.left, count), r = avgWalk(node.right, count);
    int s = l[0] + r[0] + node.val, c = l[1] + r[1] + 1;
    if (s / c == node.val) count[0]++;
    return new int[] {s, c};
}

C++

pair<int, int> avgWalk(TreeNode* node, int& count);

int averageOfSubtree(TreeNode* root) {
    int count = 0;
    avgWalk(root, count);
    return count;
}

// Returns {sum, size} of the subtree.
pair<int, int> avgWalk(TreeNode* node, int& count) {
    if (!node) return {0, 0};
    auto l = avgWalk(node->left, count);
    auto r = avgWalk(node->right, count);
    int s = l.first + r.first + node->val, c = l.second + r.second + 1;
    if (s / c == node->val) count++;
    return {s, c};
}

JavaScript

var averageOfSubtree = function(root) {
    var state = { count: 0 };
    avgWalk(root, state);
    return state.count;
};

// Returns [sum, size] of the subtree.
var avgWalk = function(node, state) {
    if (node === null) return [0, 0];
    var l = avgWalk(node.left, state), r = avgWalk(node.right, state);
    var s = l[0] + r[0] + node.val, c = l[1] + r[1] + 1;
    if (Math.floor(s / c) === node.val) state.count++;
    return [s, c];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals