[501] Find Mode in Binary Search Tree

https://leetcode.com/problems/find-mode-in-binary-search-tree/description/

• algorithms
• Easy (38.20%)
• Source Code: 501.find-mode-in-binary-search-tree.py
• Total Accepted: 53.9K
• Total Submissions: 137.5K
• Testcase Example: '[1,null,2,2]'

Given a binary search tree (BST) with duplicates, find all the mode(s) (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).

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        result = []
        if not root: return result

        self.inorder(root, result)

        table = {}
        for r in result:
            if r not in table:
                table[r] = 0
            table[r] += 1

        mx = max(table.values())
        ret = []
        for k, v in table.items():
            if v == mx: ret.append(k)

        return ret

    def inorder(self, root, result):
        if not root:
            return

        if root.left:
            self.inorder(root.left, result)

        result.append(root.val)

        if root.right:
            self.inorder(root.right, result)