# Java AC Solution

• O(n) time O(n) space

``````public class Solution {
Map<Integer, Integer> map;
int max = 0;
public int[] findMode(TreeNode root) {
if(root==null) return new int[0];
this.map = new HashMap<>();

inorder(root);

List<Integer> list = new LinkedList<>();
for(int key: map.keySet()){
if(map.get(key) == max) list.add(key);
}

int[] res = new int[list.size()];
for(int i = 0; i<res.length; i++) res[i] = list.get(i);
return res;
}

private void inorder(TreeNode node){
if(node.left!=null) inorder(node.left);
map.put(node.val, map.getOrDefault(node.val, 0)+1);
max = Math.max(max, map.get(node.val));
if(node.right!=null) inorder(node.right);
}
}
``````

Just travel the tree and count, find the those with max counts. Nothing much. Spent 10min on figuring out what is mode....

If using this method (hashmap), inorder/preorder/postorder gives the same result. Because essentially you just travel the entire nodes and count. And BST is not necessary. This method works for any tree.

• Did you consider the use of BST? I thought since it's BST, I can just put to map if left child's value is the same as node's, it did save some space but will fail since the tree can be built without duplicates in test case...

• It can be done in O(1) without considering the recursive call stack
beats 100%

``````void helper(TreeNode root, int[] var, List<Integer> result){
if(root == null) return;
helper(root.left,var,result);
var[1] = root.val==var[2] ? var[1]+1 : 1;
if(var[1] >= var[0]){
if(var[1] > var[0]) result.clear();
var[0] = var[1];
if(result.size()==0 || result.get(result.size()-1)!=root.val){
}
}
var[2] = root.val;
helper(root.right,var,result);
}
//without extra space
public int[] findMode(TreeNode root) {
List<Integer> temp = new LinkedList<>();
int[] var = new int[3]; // var[0] = max, var[1] = curr_max, var[2] = prev
helper(root,var,temp);

int[] result = new int[temp.size()];
for(int i=0;i<result.length;i++) result[i] = temp.get(i);
return result;
}

``````

For detailed Explanation: https://discuss.leetcode.com/topic/77309/java-o-1-space-solution-beats-100

• @qingyun-wu559-gmail-com You can save space by traveling twice, as said by @StefanPochmann.

• @Chidong

Not O(1) space, but smooth and clear.

• For this solution, inorder traversal is not important because preorder/postorder can work.

• @prateek470 worse case extra space O(n) , no ?

• @ndlu01 In the problem, recursive calls are not considered in space complexity.

• @prateek470

but the temp list is in the main stack, so it will always exit and consume space in the worst case..?

• Similar idea, I use post order though. Btw, the return value type int[] make our code messy. So I ask help for lambda. Thanks for sharing!

``````    public int[] findMode(TreeNode root) {
Map<Integer,Integer> freq = new HashMap<>();
int max = dfs(root, freq);
return freq.entrySet().stream().
filter(e -> e.getValue() == max).
mapToInt(e -> e.getKey()).toArray();
}

private int dfs(TreeNode root, Map<Integer,Integer> freq) {
if (root == null) return 0;
int l = dfs(root.left, freq);
int r = dfs(root.right, freq);
freq.put(root.val, freq.getOrDefault(root.val, 0) + 1);
return Math.max(freq.get(root.val), Math.max(l, r));
}
``````

• This is obviously not O(1) space. I don't know why people give so many thumb ups.
O(n) space makes this question meaningless.

• Same idea, but i think it will explore BST property later

``````
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
int max = 0;

public int[] findMode(TreeNode root) {
List<Integer> tmp = new ArrayList<>();
HashMap<Integer, Integer> map = new HashMap<>();
inOrder(root, map);
// for (Map.Entry s : map.entrySet()) {
//     if ((int)s.getValue() == max) {
//     }
// }
for (int key : map.keySet()) {
if (map.get(key) == max) {
}
}

int[] res = new int[tmp.size()];
int id = 0;
for (int num : tmp) {
res[id++] = num;
}

return res;
}
private void inOrder(TreeNode root, HashMap<Integer, Integer> map) {
if (root == null) {
return;
}
inOrder(root.left, map);
map.put(root.val, map.getOrDefault(root.val, 0) + 1);
int count = map.get(root.val);
max = Math.max(max, count);
inOrder(root.right, map);
}
}

``````

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