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
2
3
4
5
6
Given BST: [1,null,2,2]
1
\
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:

  1. 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
      44
      private 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);
      }
      Time: $O(N)$
      Space: $O(N)$
  2. 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
      58
      private 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);
      }
      Time: $O(N)$
      Space: $O(1)$