501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all the mode) (the most frequently occurred element) in the given BST.

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than or equal to the node's key.
• The right subtree of a node contains only nodes with keys greater than or equal to the node's key.
• Both the left and right subtrees must also be binary search trees.

For example: Given BST [1,null,2,2],

   1
    \
     2
    /
   2

return [2].

Note:

If a tree has more than one mode, you can return them in any order.

Follow-Up:

Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solution:

class Solution(object):
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        mode = []
        stats = [None, 0, 0]

        def find(node):
            if not node:
                return
            find(node.left)
            update(node.val)
            find(node.right)

        def update(val):
            pre, freq, max_freq = stats
            if val == pre:
                freq += 1
            else:
                freq = 1
                pre = val
            if freq == max_freq:
                mode.append(val)
            elif freq > max_freq:
                max_freq = freq
                mode[:] = [val]
            stats[:] = [pre, freq, max_freq]

        find(root)
        return mode