**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**

- Write BST Iterator class which gives the next element in_order. Now the problem reduces to finding mode in a sorted array.
- Instead of a BST iterator, we can use a recursive inorder traversal and store a class variable pre to indicate the previous integer.
- https://discuss.leetcode.com/topic/77308/4ms-java-solution-beats-100-o-1-space-recursion-stack-space-doesn-t-count

**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)