# Python solution with detailed explanation

• Solution

Find Mode in Binary Search Tree https://leetcode.com/problems/find-mode-in-binary-search-tree/

O(N) time & O(N) Space

• Use a dictionary to store the frequency of each interger. Then simply find the largest frequency and return all the associated keys.
• Note we do not use the property of BST in this solution.
``````from collections import defaultdict
class Solution(object):
def helper(self, root, cache):
if root == None:
return
cache[root.val] += 1
self.helper(root.left, cache)
self.helper(root.right, cache)
return

def findMode(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if root == None:
return []
cache = defaultdict(int)
self.helper(root, cache)
max_freq = max(cache.values())
result = [k for k,v in cache.items() if v == max_freq]
return result
``````

O(N) time and O(1) Space

Divide and Conquer

• Mode lies entirely in left subtree, or in right subtree or the middle element is the mode.
• Time would be NlogN at best and space O(1)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.