Most Frequent Subtree Sum - Practice Coding Problems

Most Frequent Subtree Sum - Problem

Given the root of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

Input & Output

Example 1 — Basic Tree

$ Input: root = [5,2,-3]

› Output: [2,-3,4]

💡 Note: Subtree sums: Node 2 has sum 2, Node -3 has sum -3, Node 5 has sum 5+2+(-3)=4. All appear once, so return all.

Example 2 — Duplicate Sums

$ Input: root = [5,2,-5]

› Output: [2]

💡 Note: Subtree sums: Node 2 has sum 2, Node -5 has sum -5, Node 5 has sum 5+2+(-5)=2. Sum 2 appears twice (most frequent), so return [2].

Example 3 — Single Node

$ Input: root = [1]

› Output: [1]

💡 Note: Only one subtree with sum 1, so it's the most frequent.

Constraints

The number of nodes in the tree is in the range [1, 10⁴]
-10⁵ ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Binary tree with node values

Calculate Sums

Find sum for each subtree

Find Most Frequent

Return sums that appear most often

Key Takeaway

🎯 Key Insight: Use post-order DFS to calculate subtree sums efficiently while tracking frequencies in a single pass

Asked in

a Amazon 15 G Google 12 f Facebook 8

The key insight is to use post-order DFS traversal to calculate subtree sums bottom-up while tracking their frequencies. The optimal approach visits each node once, calculates its subtree sum from children, and maintains a frequency map. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized DFS with Frequency Tracking	O(n)	O(n)	Single DFS traversal calculating subtree sums and tracking frequencies
Brute Force - Separate Sum and Count	O(n²)	O(n)	Calculate all subtree sums first, then count frequencies separately

Optimized DFS with Frequency Tracking — Algorithm Steps

Step 1: Perform post-order DFS traversal
Step 2: For each node, calculate subtree sum from children
Step 3: Track frequency of each sum in hash map
Step 4: Return sums with maximum frequency

Visualization

Tap to expand

Step-by-Step Walkthrough

Post-Order DFS

Visit children first, then calculate sum

Track Frequencies

Add each sum to frequency map

Find Maximum

Return sums with highest frequency

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Simple hash map using arrays
int sums[1000];
int frequencies[1000];
int uniqueCount = 0;

void addToFreqMap(int sum) {
    for (int i = 0; i < uniqueCount; i++) {
        if (sums[i] == sum) {
            frequencies[i]++;
            return;
        }
    }
    sums[uniqueCount] = sum;
    frequencies[uniqueCount] = 1;
    uniqueCount++;
}

int dfs(struct TreeNode* node) {
    if (!node) return 0;
    
    int leftSum = dfs(node->left);
    int rightSum = dfs(node->right);
    int subtreeSum = node->val + leftSum + rightSum;
    
    addToFreqMap(subtreeSum);
    
    return subtreeSum;
}

int* solution(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if (!root) return NULL;
    
    uniqueCount = 0;
    dfs(root);
    
    int maxFreq = 0;
    for (int i = 0; i < uniqueCount; i++) {
        if (frequencies[i] > maxFreq) {
            maxFreq = frequencies[i];
        }
    }
    
    int* result = malloc(uniqueCount * sizeof(int));
    for (int i = 0; i < uniqueCount; i++) {
        if (frequencies[i] == maxFreq) {
            result[(*returnSize)++] = sums[i];
        }
    }
    
    return result;
}

int main() {
    // Simplified input parsing for demonstration
    struct TreeNode* root = createNode(5);
    root->left = createNode(2);
    root->right = createNode(-3);
    
    int returnSize;
    int* result = solution(root, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        if (i > 0) printf(",");
        printf("%d", result[i]);
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single DFS traversal visits each node exactly once

✓ Linear Growth

Space Complexity

O(n)

Hash map stores at most n different sums plus recursion stack

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized DFS with Frequency Tracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler