Most Frequent Subtree Sum
Medium · Trees · Hash Table · Tree · Depth-First Search · Binary Tree
Problem
The subtree sum of a node is the sum of all values in the subtree rooted at that node, including the node itself.
Given the root of a binary tree, return the subtree sum(s) that occur most often. If several sums tie for the highest frequency, return all of them, in any order.
Examples
Input: root = [5,2,-3] Output: [-3,2,4]
The subtree sums are 2, -3 and 4, each once, so all three are returned.
Input: root = [5,2,-5] Output: [2]
The sums are 2, -5 and 2: 2 occurs twice.
Input: root = [0,2,-2,1,1] Output: [1]
The leaves 1 and 1 give 1 twice; 4, -2 and 2 appear once.
Constraints
- The number of nodes is in the range [1, 10^4]
- -10^5 <= Node.val <= 10^5
Approaches
- Sum every subtree from scratch — time O(n * h), space O(n)
Follow-up
Bottom-up sums answer any question about subtree totals in one pass. The use cases count the subtrees with one given sum and find the largest subtree sum.
Related problems
Start free on Cariara · Coding problems · System design studio
