# LINKEDIN
"""
    SOLVED -- LEETCODE#508
    Given a binary tree, find the most frequent subtree sum.
    Example:
      3
     / \
    1   -3
    The above tree has 3 subtrees. The root node with 3, and the 2 leaf nodes, 
    which gives us a total of 3 subtree sums. The root node has a sum of 1 (3 + 1 + -3), 
    the left leaf node has a sum of 1, and the right leaf node has a sum of -3. 
    Therefore the most frequent subtree sum is 1.
    If there is a tie between the most frequent sum, you can return any one of them.
"""


class Node():
    def __init__(self, value, left=None, right=None):
        self.val = value
        self.left = left
        self.right = right

from collections import defaultdict

def subtree_sum(root, sums):
    if not root: return 0
    S = root.val + subtree_sum(root.left, sums) + subtree_sum(root.right, sums)
    sums[S] += 1
    return S

def most_freq_subtree_sum(root):
    sums = defaultdict(int)
    subtree_sum(root, sums)

    sol = list(sums.keys())[0]
    for x in sums:
        if sums[x] > sums[sol]:
            sol = x

    return sol

root = Node(3, Node(1), Node(-3))
print(most_freq_subtree_sum(root))
# 1
