grid47 Exploring patterns and algorithms
Sep 17, 2024
6 min read
Solution to LeetCode 501: Find Mode in Binary Search Tree Problem
Given the root of a binary search tree (BST) with possible duplicates, return the mode(s) (i.e., the most frequently occurring element) in the tree. If there are multiple modes, return them in any order.
Problem
Approach
Steps
Complexity
Input: The input is the root node of a binary search tree (BST), which may contain duplicate values.
Example: [3, 2, 4, 2, 2, 5, 5]
Constraints:
• 1 <= Number of nodes <= 10^4
• -10^5 <= Node.val <= 10^5
Output: The output should be an array of integers representing the mode(s) of the tree, i.e., the most frequently occurring values.
Example: [2, 5]
Constraints:
• The output array contains the mode(s) from the tree.
Goal: The goal is to identify the most frequent element(s) in a binary search tree with potential duplicates.
Steps:
• 1. Perform an in-order traversal of the tree to visit nodes in ascending order.
• 2. Track the frequency of each node's value as you traverse.
• 3. Identify the mode(s) by comparing frequencies and storing the most frequent values.
Goal: The tree contains at least one node, and the number of nodes is within the specified limit.
Steps:
• 1 <= Number of nodes <= 10^4
• -10^5 <= Node.val <= 10^5
Assumptions:
• The binary tree is well-formed with valid BST properties.
• The tree may contain duplicate values, which should be handled.
• Input: [3, 2, 4, 2, 2, 5, 5]
• Explanation: In this example, the value 2 appears most frequently (3 times), and 5 appears twice, so the modes are [2, 5].
Approach: The approach involves performing an in-order traversal of the tree to count the frequency of each element and identify the mode(s).
Observations:
• In-order traversal ensures nodes are visited in ascending order.
• As we traverse, we can keep track of the frequency of node values and update the mode accordingly.
• We need to maintain a running frequency count and determine the highest frequency encountered during the traversal.
Steps:
• 1. Initialize a variable to track the current frequency and the maximum frequency.
• 2. Perform an in-order traversal of the tree.
• 3. For each node, compare its value to the previous node's value and update the frequency count.
• 4. If the current frequency exceeds the maximum frequency, update the result list.
• 5. Return the list of modes after traversal is complete.
Empty Inputs:
• The tree will always have at least one node.
Large Inputs:
• The solution should handle trees with up to 10,000 nodes efficiently.
Special Values:
• The tree may contain nodes with negative values and large values (up to 10^5), which should be handled correctly.
Constraints:
• Ensure that the traversal and frequency count is optimized for large trees.
int maxFreq =0, currFreq =0, precursor = INT_MIN;
vector<int> res;
vector<int> findMode(TreeNode *root)
{
inorderTraversal(root);
return res;
}
voidinorderTraversal(TreeNode *root)
{
if (root ==NULL) return; // Stop condition
inorderTraversal(root->left); // Traverse left subtree
if (precursor == root->val) currFreq++;
else currFreq =1;
if (currFreq > maxFreq)
{// Current node value has higher frequency than any previous visited
res.clear();
maxFreq = currFreq;
res.push_back(root->val);
}
elseif (currFreq == maxFreq)
{// Current node value has a frequency equal to the highest of previous visited
res.push_back(root->val);
}
precursor = root->val; // Update the precursor
inorderTraversal(root->right); // Traverse right subtree
}
1 : Variable Initialization
int maxFreq =0, currFreq =0, precursor = INT_MIN;
Initializes variables `maxFreq` to track the highest frequency, `currFreq` to track the current frequency of a node, and `precursor` to store the previous node value during traversal.
2 : Variable Initialization
vector<int> res;
Declares a vector `res` that will hold the values with the highest frequency.
3 : Method Definition
vector<int> findMode(TreeNode *root)
Defines the method `findMode` which takes a binary tree root node `root` and returns a vector of integers that represent the most frequent values in the tree.
4 : Method Call
inorderTraversal(root);
Calls the helper method `inorderTraversal` to perform an inorder traversal of the tree and update the `res` vector.
5 : Return Statement
return res;
Returns the vector `res`, which contains the values with the highest frequency in the tree.
6 : Method Definition
void inorderTraversal(TreeNode *root)
Defines the helper method `inorderTraversal` that performs an inorder traversal of the tree to track node frequencies.
7 : Base Case
if (root ==NULL) return; // Stop condition
Checks if the current node is `NULL`. If it is, the function returns, serving as the stop condition for recursion.
8 : Recursive Call
inorderTraversal(root->left); // Traverse left subtree
Recursively calls `inorderTraversal` on the left child of the current node to traverse the left subtree.
9 : Frequency Check
if (precursor == root->val) currFreq++;
Checks if the current node's value is equal to the `precursor` (previous node value). If so, increments the current frequency `currFreq`.
10 : Frequency Reset
else currFreq =1;
If the current node's value is different from the `precursor`, resets the current frequency `currFreq` to 1.
11 : Frequency Comparison
if (currFreq > maxFreq)
Compares the current frequency `currFreq` with the maximum frequency `maxFreq`.
12 : Result Update
res.clear();
Clears the `res` vector to remove previously stored values, as the current node has a higher frequency.
13 : Maximum Frequency Update
maxFreq = currFreq;
Updates the `maxFreq` to the current frequency `currFreq`.
14 : Result Update
res.push_back(root->val);
Adds the current node's value to the `res` vector as it now has the highest frequency.
15 : Frequency Comparison
elseif (currFreq == maxFreq)
If the current frequency is equal to the `maxFreq`, add the current node value to the results.
16 : Result Update
res.push_back(root->val);
Adds the current node's value to the `res` vector, as it matches the maximum frequency.
17 : Update Precursor
precursor = root->val; // Update the precursor
Updates the `precursor` to the current node's value to be used in the next comparison.
18 : Recursive Call
inorderTraversal(root->right); // Traverse right subtree
Recursively calls `inorderTraversal` on the right child of the current node to traverse the right subtree.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The time complexity is O(n), where n is the number of nodes in the tree, as each node is visited once during the in-order traversal.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the space required to store the result list and the recursion stack during the in-order traversal.
