Find Mode in Binary Search Tree

• Initialize a HashMap<Integer, Integer> to store the frequency of each number.
• Define a traversal function (e.g., DFS or BFS) that takes a node as input.
• Inside the traversal function, for the current node, update its count in the counts map: counts.put(node.val, counts.getOrDefault(node.val, 0) + 1).
• Recursively call the traversal function for the left and right children.
• Start the traversal from the root.
• After the traversal is complete, find the maximum frequency (maxFreq) among all values in the counts map.
• Initialize an empty list modes.
• Iterate through the counts map again. If a key's value (frequency) is equal to maxFreq, add the key to the modes list.
• Convert the modes list to an integer array and return it.

The most intuitive way to solve this problem is to count the occurrences of each number. A hash map is a perfect data structure for this. We can traverse the tree using any order (pre-order, in-order, or post-order) and populate a hash map where the key is the node's value and the value is its frequency. After the first traversal populates the map, we perform a second pass over the map's entries to determine the highest frequency. Finally, a third pass over the map collects all the numbers that have this maximum frequency.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    private Map<Integer, Integer> counts = new HashMap<>();18 19    public int[] findMode(TreeNode root) {20        if (root == null) {21            return new int[0];22        }23        24        traverse(root);25        26        int maxFreq = 0;27        for (int freq : counts.values()) {28            maxFreq = Math.max(maxFreq, freq);29        }30        31        List<Integer> modes = new ArrayList<>();32        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {33            if (entry.getValue() == maxFreq) {34                modes.add(entry.getKey());35            }36        }37        38        return modes.stream().mapToInt(i->i).toArray();39    }40 41    private void traverse(TreeNode node) {42        if (node == null) {43            return;44        }45        counts.put(node.val, counts.getOrDefault(node.val, 0) + 1);46        traverse(node.left);47        traverse(node.right);48    }49}

• Pass 1: Find Maximum Frequency
  • Initialize maxFreq = 0, currentCount = 0, and prevVal to a value outside the range of node values.
  • Perform an in-order traversal. For each node, if its value is the same as the previous one, increment currentCount. Otherwise, reset currentCount to 1. Update maxFreq with the maximum currentCount seen so far.
  • After the traversal, do a final update for maxFreq to account for the last sequence of numbers.
• Pass 2: Collect Modes
  • Initialize an empty list modes.
  • Reset currentCount and prevVal.
  • Perform a second in-order traversal.
  • Count the occurrences of the current value sequence, same as in Pass 1.
  • When a sequence of identical values ends, check if its count is equal to maxFreq. If it is, add the value to the modes list.
  • After the traversal, perform a final check for the last sequence of values.
• Convert the modes list to an array and return.

To avoid the O(N) space complexity of the HashMap, we can utilize the BST property. An in-order traversal visits nodes in a sorted manner, which groups all identical values together. This allows us to count frequencies without a map.

However, we don't know what the maximum frequency is until we've seen all the numbers. This necessitates a two-pass approach:

1. First Pass: Perform an in-order traversal solely to find the value of the maximum frequency (maxFreq). We keep track of the current number's streak (currentCount) and update maxFreq whenever a longer streak is found.
2. Second Pass: Perform another in-order traversal. This time, we know the maxFreq. We again count the streaks of numbers, and if a number's streak count equals maxFreq, we add it to our result list.

This method satisfies the follow-up's space constraint but at the cost of traversing the entire tree twice.

1class Solution {2    private int currentCount = 0;3    private int maxFreq = 0;4    private Integer prevVal = null;5    private List<Integer> modes = new ArrayList<>();6 7    public int[] findMode(TreeNode root) {8        // Pass 1: Find the max frequency9        inorderPass1(root);10        11        // Reset for Pass 212        prevVal = null;13        currentCount = 0;14        15        // Pass 2: Collect the modes16        inorderPass2(root);17        18        return modes.stream().mapToInt(i -> i).toArray();19    }20 21    private void handleValuePass1(Integer val) {22        if (prevVal != null && prevVal.equals(val)) {23            currentCount++;24        } else {25            currentCount = 1;26        }27        maxFreq = Math.max(maxFreq, currentCount);28        prevVal = val;29    }30 31    private void inorderPass1(TreeNode node) {32        if (node == null) return;33        inorderPass1(node.left);34        handleValuePass1(node.val);35        inorderPass1(node.right);36    }37 38    private void handleValuePass2(Integer val) {39        if (prevVal != null && prevVal.equals(val)) {40            currentCount++;41        } else {42            currentCount = 1;43        }44        if (currentCount == maxFreq) {45            // Add only the first element of a mode sequence46            if (modes.isEmpty() || !modes.get(modes.size() - 1).equals(val)) {47                modes.add(val);48            }49        }50        prevVal = val;51    }52 53    private void inorderPass2(TreeNode node) {54        if (node == null) return;55        inorderPass2(node.left);56        handleValuePass2(node.val);57        inorderPass2(node.right);58    }59}

• Initialize class-level variables: List<Integer> modes, int maxFreq = 0, Integer prevVal = null, int currentCount = 0.
• Create a recursive inorder helper function that takes a TreeNode.
• The main findMode function will initialize the modes list, call inorder(root), and then convert the modes list to an int[].
• inorder(node) logic:
  • If node is null, return.
  • Recursively call inorder(node.left).
  • Process the current node:
    • If prevVal is not null and node.val is the same as prevVal, increment currentCount.
    • Otherwise (it's the first node or a new value), reset currentCount to 1.
  • Update modes based on currentCount:
    • If currentCount > maxFreq: We've found a new, more frequent mode. Update maxFreq = currentCount, clear the modes list, and add node.val to it.
    • Else if currentCount == maxFreq: We've found another value with the same top frequency. Add node.val to the modes list.
  • Update prevVal = node.val to prepare for the next node.
  • Recursively call inorder(node.right).

We can optimize the two-pass approach into a single pass. The key insight is that during a single in-order traversal, we can update our list of modes dynamically. We maintain the frequency of the current element (currentCount) and the maximum frequency found so far (maxFreq).

As we traverse:

• If the current element's frequency (currentCount) becomes greater than maxFreq, it means we have found a new unique mode. We update maxFreq, clear our previous list of modes, and add the current element as the new mode.
• If currentCount equals maxFreq, it means we have found another element that is also a mode. We simply add it to our list of modes.
• If currentCount is less than maxFreq, we do nothing.

This allows us to determine the modes in a single pass, making it the most optimal solution.

1class Solution {2    private List<Integer> modes = new ArrayList<>();3    private int maxFreq = 0;4    private Integer prevVal = null;5    private int currentCount = 0;6 7    public int[] findMode(TreeNode root) {8        inorder(root);9        10        int[] result = new int[modes.size()];11        for (int i = 0; i < modes.size(); i++) {12            result[i] = modes.get(i);13        }14        return result;15    }16 17    private void inorder(TreeNode node) {18        if (node == null) {19            return;20        }21 22        // Traverse left subtree23        inorder(node.left);24 25        // Process current node26        if (prevVal != null && prevVal == node.val) {27            currentCount++;28        } else {29            currentCount = 1;30        }31 32        // Update modes list33        if (currentCount > maxFreq) {34            maxFreq = currentCount;35            modes.clear();36            modes.add(node.val);37        } else if (currentCount == maxFreq) {38            modes.add(node.val);39        }40        41        prevVal = node.val;42 43        // Traverse right subtree44        inorder(node.right);45    }46}