Find Mode in Binary Search Tree in Java
Finding the mode in a Binary Search Tree is a crucial problem in computer science and data structures. The mode is the value that appears most frequently in a BST. Finding the mode in a BST provides valuable insights into the distribution of values within the tree.
Example 1:
![Find Mode in Binary Search Tree in Java](https://static.tutorialandexample.com/java/find-mode-in-binary-search-tree-in-java1.png)
Input: root = [1, null,2,2]
Output: 2
Using DFS
The code uses the Deep-First Search (DFS) approach to traverse a binary search tree (BST) and find the mode(s), which are the most frequently occurring values in the tree. The code includes a ModeFinder Class, a findMode method, a frequency map, a tree traversal method, a frequency map, a recursive traverseBST method, a main method, and a binary search tree. The method initializes a HashMap called `frequencyMap`, populates the tree with the frequencies of each node, and updates the frequency map. The method iterates through the keys of the `frequencyMap` to find the mode, keeping track of the maximum frequency and updating it whenever it finds a higher frequency. The main method creates a binary search tree and initializes a `ModeFinder` object to find the mode in the tree.
Here's an implementation of finding mode in a binary search tree using dfs:
FileName: ModeFinder.java
import java.util.Map; import java.util.HashMap; import java.util.List; import java.util.ArrayList; public class ModeFinder { // Map to store the frequency of each node value MapfrequencyMap; // Method to find mode(s) in the binary search tree public int[] findMode(TreeNode root) { frequencyMap = new HashMap<>(); traverseBST(root); // Variables to track the maximum frequency and mode(s) int maxFrequency = -1; List modes = new ArrayList<>(); for (int key : frequencyMap.keySet()) { int frequency = frequencyMap.get(key); // If the current frequency is greater than the maximum frequency found so far, //Update the maximum frequency and clear the modes list to add the new mode if (maxFrequency < frequency) { maxFrequency = frequency; modes.clear(); modes.add(key); continue; } if (maxFrequency == frequency) { modes.add(key); } } int[] result = new int[modes.size()]; for (int i = 0; i < modes.size(); i++) { result[i] = modes.get(i); } return result; } // Method to traverse the binary search tree and populate the frequency map private void traverseBST(TreeNode node) { // Base case: if the node is null, return if (node == null) return; // Incrementing the frequency count for the current node value if (frequencyMap.containsKey(node.value)) { frequencyMap.put(node.value, frequencyMap.get(node.value) + 1); } else { frequencyMap.put(node.value, 1); } // Recursively traversing the left and right subtrees traverseBST(node.left); traverseBST(node.right); } public static void main(String[] args) { TreeNode root = new TreeNode(1); root.right = new TreeNode(2); root.right.left = new TreeNode(2); // Creating the mode finder object ModeFinder modeFinder = new ModeFinder(); // Finding the mode int[] output = modeFinder.findMode(root); System.out.println("Input: root = [1,null,2,2]"); System.out.print("Output: ["); for (int i = 0; i < output.length; i++) { System.out.print(output[i]); if (i < output.length - 1) System.out.print(", "); } System.out.println("]"); } } class TreeNode { int value; TreeNode left; TreeNode right; // Constructor to initialize the node with a given value TreeNode(int val) { value = val; } }
Output:
Input: root = [1, null,2,2] Output: [2]
Complexity analysis: The Depth-First Search (DFS) approach is used to analyze the complexity of a code. The time complexity is O(n + m), as traversing the binary search tree takes O(n) and O(m) for iterating through the frequency map. The space complexity is O(n) due to the space used for the frequency map and the recursive call stack during traversal. The overall space complexity is O(n), as the tree's height can be O(n) in worst-case scenarios.
Using Inorder Traversal
The code consists of three classes: the ModeFinder class, the TreeNode class, and the Main Method. The ModeFinder class is responsible for finding the mode in a binary tree, maintaining three variables: previous, currentCount, and maxCount. The TreeNode class represents a node in the binary tree with three fields: value, left, and right. The Main Method creates a binary tree with a specified structure, creates an instance of the ModeFinder class, and finds the mode using the findMode method.
Here's an implementation of finding mode in a binary search tree using inorder traversal:
FileName: ModeFinder1.java
import java.util.*; public class ModeFinder1 { TreeNode previous = null; int currentCount = 1; int maxCount = 0; // Method to find mode in the binary tree public int[] findMode(TreeNode root) { if (root == null) return new int[0]; // List to store the mode(s) Listmodes = new ArrayList<>(); // Traverse the tree and find mode(s) traverseAndFindModes(root, modes); // Convert the list of mode to an array int[] result = new int[modes.size()]; for (int i = 0; i < modes.size(); i++) { result[i] = modes.get(i); } return result; } // Recursive method to traverse the tree and find mode(s) private void traverseAndFindModes(TreeNode root, List modes) { // Base case: if the root is null, return if (root == null) return; traverseAndFindModes(root.left, modes); // Update the count based on the value of the current node and the previous node if (previous != null) { if (root.value == previous.value) { currentCount++; } else { currentCount = 1; } } // Update the maximum count and modes list if (currentCount > maxCount) { maxCount = currentCount; modes.clear(); modes.add(root.value); } else if (currentCount == maxCount) { modes.add(root.value); } // Update the previous node and traverse the right subtree previous = root; traverseAndFindModes(root.right, modes); } public static void main(String[] args) { TreeNode root = new TreeNode(1); root.right = new TreeNode(2); root.right.left = new TreeNode(2); // Creating the mode finder object ModeFinder1 modeFinder = new ModeFinder1(); // Finding the mode for the tree int[] output = modeFinder.findMode(root); System.out.println("Input: root = [1,null,2,2]"); System.out.print("Output: ["); for (int i = 0; i < output.length; i++) { System.out.print(output[i]); if (i < output.length - 1) System.out.print(", "); } System.out.println("]"); } } class TreeNode { int value; TreeNode left; TreeNode right; // Constructor to initialize the node with a given value TreeNode(int val) { value = val; } }
Output:
Input: root = [1,null,2,2] Output: [2]
Complexity analysis: The code 'traverseAndFindModes' uses a depth-first traversal of a binary tree, resulting in a time complexity of O(n), where n is the number of nodes in the tree. The time complexity is dominated by the tree traversal, with a total time complexity of O(n). The space complexity is determined by the maximum depth of the recursion, which is the height of the binary tree. The space complexity for the'modes' list is proportional to the number of modes found, with a total space complexity of O(n).