Question

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.
For example:
Given BST [1,null,2,2],

   1
    \
     2
    /
   2

 

return [2].

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

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

Solution

  • Method 1: HashMap + dfs ```Java /**
    • Definition for a binary tree node.
    • public class TreeNode {
    • int val;
    • TreeNode left;
    • TreeNode right;
    • TreeNode(int x) { val = x; }
    • } */ class Solution { private Map<Integer, Integer> map; private int max = Integer.MIN_VALUE; public int[] findMode(TreeNode root) { if(root == null) return new int[]{}; this.map = new HashMap<>(); dfs(root); int count = 0; for(int i : map.values()){ if(i == max) count++; } int[] res = new int[count]; int i = 0; for(Map.Entry<Integer, Integer> entry : map.entrySet()){ if(entry.getValue() == max) res[i++] = entry.getKey(); } return res; } private void dfs(TreeNode node){ if(node == null) return; Integer count = map.containsKey(node.val) ? map.get(node.val): 0; map.put(node.val, count + 1); this.max = Math.max(max, count + 1); dfs(node.left); dfs(node.right); } } ```