Find Mode In Binary Search Tree - Leetcode Solution

Problem Statement:

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.

Example:

Input: 1 /
2 2 /
2 3

Output: [2]

Explanation: 2 has appeared three times in the BST, so it is the mode.

Approach:

In order to find the mode of the given BST, we can use the concepts of Inorder Traversal and HashMap. Here are the steps involved in the approach:

1. Initialize a HashMap to store the frequency of each node value in the given BST.

2. Perform Inorder Traversal of the BST and update the frequency of each node value in the HashMap.

3. Find the maximum frequency value in the HashMap.

4. Add all the node values with the maximum frequency value to a List.

5. Return the List as the output.

Detailed Solution:

Let's now discuss the above steps in detail:

Step 1: Initialize a HashMap to store the frequency of each node value in the given BST.

We initialize a Hashmap with Integer as Key and Integer as Value, to store the frequency of each node value in the given BST.

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

Step 2: Perform Inorder Traversal of the BST and update the frequency of each node value in the HashMap.

We perform Inorder Traversal of the BST using a recursive approach. For each node, we update its frequency count in the HashMap.

public void inorder(TreeNode root, HashMap<Integer, Integer> map) { if (root == null) { return; } inorder(root.left, map); map.put(root.val, map.getOrDefault(root.val, 0) + 1); // update frequency count inorder(root.right, map); }

Step 3: Find the maximum frequency value in the HashMap.

We find the maximum frequency count value in the HashMap.

int maxFreq = 0; for (int freq : map.values()) { maxFreq = Math.max(maxFreq, freq); }

Step 4: Add all the node values with the maximum frequency value to a List.

We add all the node values with the maximum frequency count to a List.

List<Integer> modes = new ArrayList<>(); for (int key : map.keySet()) { if (map.get(key) == maxFreq) { modes.add(key); } }

Step 5: Return the List as the output.

Finally, we return the List as the output.

return modes;

Time Complexity:

The time complexity of the above approach is O(n), where n is the number of nodes in the BST. This is because we are performing Inorder Traversal of the BST only once.

Space Complexity:

The space complexity of the above approach is O(n), where n is the number of nodes in the BST. This is because we are storing the frequency count of each node in a HashMap and the maximum frequency count can be n, in case of all nodes having the same value.

1