Most Common Subtree Total

Medium

You are given the root of a binary tree. For every node, compute its subtree total: the node's own value plus the values of all its descendants. Among all these totals, find the ones that occur most often. If one total wins outright, return a list containing just it; if several share the top count, return all of them. The order of the answer does not matter.

Example 1

root=tree_node([3, 1, -4]) → [1, -4, 0]

The subtree totals are 1 for leaf 1, -4 for leaf -4, and 3 + 1 - 4 = 0 for the root. Each appears once, so all three are returned.

Example 2

root=tree_node([6, 2, -2]) → [2, -2, 6]

The totals are 2, -2 and 6 + 2 - 2 = 6, again once each.

Example 3

root=tree_node([4, 2, 6, None, None, 2]) → [2]

The two leaves give 2 and 2, node 6 with its left child 2 gives 8, and the root gives 4 + 2 + 8 = 14. The value 2 is the most frequent.

Constraints

The tree has between 1 and 10⁵ nodes
-10⁵ ≤ node value ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Hash Table Binary Tree

Similar problems

Tree Columns, Top Down Medium Path Totals in a Coded Tree Medium Smallest Cover of the Bottom Row Medium Where the Deepest Leaves Meet Medium Hops Between Two Keys Medium

Input

root=tree_node([3, 1, -4])

Expected

[1, -4, 0]

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.