Reference: LeetCode

Difficulty: Easy

## Problem

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.

**Note:** If a tree has more than one mode, you can return them in any order.

**Example:**

1 | Given BST: [1,null,2,2] |

**Follow up:** Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

## Analysis

**Methods:**

- Hash Map
- In the inorder traversal, we do the counting work and use a hash map to store the values. In the meanwhile, we calculate the
`maxCount`

. - Iterate the map and add those keys that satisfy the requirement.
- Convert
`List<Integer>`

to`int[]`

in a for-loop.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44private int maxCount = Integer.MIN_VALUE;

public int[] findMode(TreeNode root) {

if (root == null) {

return new int[] {};

}

Map<Integer, Integer> map = new HashMap<>();

inorder(root, map);

// count

List<Integer> resultList = new ArrayList<>();

for (int key : map.keySet()) {

if (map.get(key) == maxCount) {

resultList.add(key);

}

}

// result - convert from List<Integer> to int[] is very annoying, but it is the only to do so.

int[] result = new int[resultList.size()];

for (int i = 0; i < result.length; ++i) {

result[i] = resultList.get(i);

}

return result;

}

private void inorder(TreeNode root, Map<Integer, Integer> map) {

if (root == null) {

return;

}

inorder(root.left, map);

int count;

if (map.containsKey(root.val)) {

count = map.get(root.val) + 1;

map.put(root.val, count);

} else {

count = 1;

map.put(root.val, count);

}

maxCount = Math.max(maxCount, count);

inorder(root.right, map);

}

- In the inorder traversal, we do the counting work and use a hash map to store the values. In the meanwhile, we calculate the

**Time:** $O(N)$

**Space:** $O(N)$

- Get Max First
- In the first traversal, calculate the
`maxCount`

, later we can add those integers to the list directly in the second traversal.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58private Integer preVal = null;

private int count = 0;

private int maxCount = Integer.MIN_VALUE;

public int[] findMode(TreeNode root) {

if (root == null) {

return new int[] {};

}

List<Integer> result = new ArrayList<>();

preVal = null; getMax(root);

preVal = null; getResult(root, result);

// convert to int[]

int[] ret = new int[result.size()];

for (int i = 0; i < ret.length; ++i) {

ret[i] = result.get(i);

}

return ret;

}

private void getMax(TreeNode root) {

if (root == null) {

return;

}

getMax(root.left);

if (preVal != null && preVal == root.val) { // same

count += 1;

maxCount = Math.max(maxCount, count);

} else { // not same

count = 1;

preVal = root.val;

maxCount = Math.max(maxCount, count);

}

getMax(root.right);

}

private void getResult(TreeNode root, List<Integer> result) {

if (root == null) {

return;

}

getResult(root.left, result);

if (preVal != null && preVal == root.val) { // same

count += 1;

} else { // not same

count = 1;

preVal = root.val;

}

if (count == maxCount) {

result.add(root.val);

}

getResult(root.right, result);

}

- In the first traversal, calculate the

**Time:** $O(N)$

**Space:** $O(1)$

Comment