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