> For the complete documentation index, see [llms.txt](https://emmaguo100.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emmaguo100.gitbook.io/leetcode/04-10-2022-501.-find-mode-in-binary-search-tree.md).

# 04/10/2022 501. Find Mode in Binary Search Tree

Method: we can inorder traverse this BST as inorder traversal gives us the non decreasing order of node val. We use TreeNode prev to record the previous node. If the prev == null or prev.val != root.val, we set the count = 1, else we increment count. Then we compare count and maxCount, if count == maxCount, we can add the root.val into result list. If the count < maxCount, we clear the result, and add root.val into result and also update the maxCount.

Time O(N)

Space O(N)

```
// Some code
class Solution {
    TreeNode prev;
    int count;
    int maxCount;
    List<Integer> result = new ArrayList<>();
    
    public int[] findMode(TreeNode root) {
        dfs(root);
        int[] res = new int[result.size()];
        for (int i = 0; i < result.size(); i++){
            res[i] = result.get(i);
        }
        return res;
    }
    private void dfs(TreeNode root){
        if (root == null) return;
        dfs(root.left);
        if (prev == null || prev.val != root.val){
            count = 1;
        } else{
            count++;
        }
        if (count == maxCount){
            result.add(root.val);
        }
        if (count > maxCount){
            result.clear();
            result.add(root.val);
            maxCount = count;
        }
        prev = root;
        dfs(root.right);
    }
}
```