# PLEASE UPVOTE IF IT HELPED\n\n---\n\n\n# Approaches\n*(Also explained in the code)*\n\n#### **Approach 1(Counting with Hash Maps)**\n1. The findMode function is designed to find the mode(s) of a binary search tree (BST). It uses an unordered map counter to store the frequency of values encountered in the BST.\n\n1. The dfs function is a helper function for depth-first search (DFS). It recursively traverses the BST, updating the frequency counter for each node\'s value.\n\n1. In the findMode function, it calculates the maximum frequency (maxFreq) by iterating through the counter map.\n\n1. Another iteration through the counter map identifies values with a frequency equal to maxFreq and adds them to the ans vector. These are the mode(s) of the BST.\n\n1. The function returns the ans vector containing the mode(s) of the BST.\n\n# Complexity\n- Time complexity:\n $$O(n)$$\n \n\n- Space complexity:\n $$O(n)$$\n \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n // Function to find the mode(s) of a binary search tree (BST).\n vector findMode(TreeNode* root) {\n // Create an unordered map to store the frequency of each value encountered in the BST.\n unordered_map counter;\n \n // Call the depth-first search (DFS) function to traverse the tree and populate the counter.\n dfs(root, counter);\n\n // Initialize a variable to keep track of the maximum frequency encountered.\n int maxFreq = 0;\n\n // Iterate through the counter to find the maximum frequency.\n for (auto& [key, val] : counter) {\n maxFreq = max(maxFreq, val);\n }\n\n // Create a vector to store the mode(s), which are the values with maximum frequency.\n vector ans;\n\n // Iterate through the counter again to find the values with maximum frequency and add them to the \'ans\' vector.\n for (auto& [key, val] : counter) {\n if (val == maxFreq) {\n ans.push_back(key);\n }\n }\n\n // Return the \'ans\' vector containing the mode(s) of the BST.\n return ans;\n }\n \n // DFS function to traverse the BST and update the frequency counter.\n void dfs(TreeNode* node, unordered_map& counter) {\n // Base case: If the current node is nullptr, return.\n if (node == nullptr) {\n return;\n }\n\n // Increment the frequency counter for the current node\'s value.\n counter[node->val]++;\n\n // Recursively traverse the left and right subtrees.\n dfs(node->left, counter);\n dfs(node->right, counter);\n }\n};\n\n\n```\n\n```C []\n\n\nstruct TreeNode {\n int val;\n struct TreeNode *left;\n struct TreeNode *right;\n};\n\nstruct TreeNode* createNode(int val) {\n struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n node->val = val;\n node->left = NULL;\n node->right = NULL;\n return node;\n}\n\nstruct ModeResult {\n int* modes;\n int count;\n};\n\nstruct ModeResult findMode(struct TreeNode* root) {\n struct ModeResult result;\n result.modes = NULL;\n result.count = 0;\n\n if (root == NULL) {\n return result;\n }\n\n // Create an array to store the frequency of each value encountered in the BST.\n int* counter = (int*)calloc(INT_MAX, sizeof(int));\n\n // Call the DFS function to traverse the tree and populate the counter.\n dfs(root, counter);\n\n int maxFreq = 0;\n\n // Iterate through the counter to find the maximum frequency.\n for (int i = 0; i < INT_MAX; i++) {\n maxFreq = maxFreq > counter[i] ? maxFreq : counter[i];\n }\n\n // Create an array to store the mode(s), which are the values with maximum frequency.\n int* ans = (int*)malloc(sizeof(int) * maxFreq);\n int ansCount = 0;\n\n // Iterate through the counter again to find the values with maximum frequency and add them to the \'ans\' array.\n for (int i = 0; i < INT_MAX; i++) {\n if (counter[i] == maxFreq) {\n ans[ansCount++] = i;\n }\n }\n\n free(counter);\n\n result.modes = ans;\n result.count = ansCount;\n return result;\n}\n\nvoid dfs(struct TreeNode* node, int* counter) {\n if (node == NULL) {\n return;\n }\n\n // Increment the frequency counter for the current node\'s value.\n counter[node->val]++;\n\n // Recursively traverse the left and right subtrees.\n dfs(node->left, counter);\n dfs(node->right, counter);\n}\n\n\n\n```\n```Java []\nclass Solution {\n public int[] findMode(TreeNode root) {\n Map counter = new HashMap();\n dfs(root, counter);\n int maxFreq = 0;\n \n for (int key : counter.keySet()) {\n maxFreq = Math.max(maxFreq, counter.get(key));\n }\n \n List ans = new ArrayList();\n for (int key : counter.keySet()) {\n if (counter.get(key) == maxFreq) {\n ans.add(key);\n }\n }\n \n int[] result = new int[ans.size()];\n for (int i = 0; i < ans.size(); i++) {\n result[i] = ans.get(i);\n }\n \n return result;\n }\n \n public void dfs(TreeNode node, Map counter) {\n if (node == null) {\n return;\n }\n \n counter.put(node.val, counter.getOrDefault(node.val, 0) + 1);\n dfs(node.left, counter);\n dfs(node.right, counter);\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def findMode(self, root: Optional[TreeNode]) -> List[int]:\n def dfs(node, counter):\n if not node:\n return\n \n counter[node.val] += 1\n dfs(node.left, counter)\n dfs(node.right, counter)\n \n counter = defaultdict(int)\n dfs(root, counter)\n max_freq = max(counter.values())\n \n ans = []\n for key in counter:\n if counter[key] == max_freq:\n ans.append(key)\n \n return ans\n\n\n```\n```javascript []\nclass TreeNode {\n constructor(val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n}\n\nclass Solution {\n findMode(root) {\n const counter = new Map();\n this.dfs(root, counter);\n\n let maxFreq = 0;\n\n for (const [key, val] of counter) {\n maxFreq = Math.max(maxFreq, val);\n }\n\n const ans = [];\n\n for (const [key, val] of counter) {\n if (val === maxFreq) {\n ans.push(key);\n }\n }\n\n return ans;\n }\n\n dfs(node, counter) {\n if (node === null) {\n return;\n }\n\n if (counter.has(node.val)) {\n counter.set(node.val, counter.get(node.val) + 1);\n } else {\n counter.set(node.val, 1);\n }\n\n this.dfs(node.left, counter);\n this.dfs(node.right, counter);\n }\n}\n\n```\n\n\n---\n#### **Approach 2(DFS)**\n1. The findMode function is designed to find the mode(s) of a binary search tree (BST) using an iterative approach. It employs a stack to perform the traversal.\n\n1. An unordered map called counter is used to store the frequency of values encountered in the BST.\n\n1. A stack named stack is created to facilitate iterative tree traversal. Initially, it is loaded with the root of the tree.\n\n1. The code enters a loop to perform iterative tree traversal while the stack is not empty. It processes nodes in a depth-first manner.\n\n1. For each node, it increments the frequency counter for the node\'s value in the counter map.\n\n1. If the current node has a left child, it is pushed onto the stack for later processing.\n\n1. If the current node has a right child, it is also pushed onto the stack for later processing.\n\n1. After completing the traversal, it calculates the maximum frequency encountered.\n\n1. A vector ans is created to store the mode(s), which are the values with the maximum frequency.\n\n1. The code iterates through the counter map again to find the values with the maximum frequency and adds them to the ans vector.\n\n1. Finally, the function returns the ans vector containing the mode(s) of the BST.\n\n# Complexity\n- Time complexity:\n $$O(n)$$\n \n\n- Space complexity:\n $$O(n)$$\n \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n // Function to find the mode(s) of a binary search tree (BST) using an iterative approach.\n vector findMode(TreeNode* root) {\n // Create an unordered map to store the frequency of each value encountered in the BST.\n unordered_map counter;\n \n // Create a stack to facilitate iterative tree traversal.\n vector stack;\n stack.push_back(root);\n \n // Perform iterative tree traversal using a stack.\n while (!stack.empty()) {\n TreeNode* node = stack.back();\n stack.pop_back();\n\n // Increment the frequency counter for the current node\'s value.\n counter[node->val]++;\n\n // If the current node has a left child, push it onto the stack for later processing.\n if (node->left != nullptr) {\n stack.push_back(node->left);\n }\n\n // If the current node has a right child, push it onto the stack for later processing.\n if (node->right != nullptr) {\n stack.push_back(node->right);\n }\n }\n \n // Initialize a variable to keep track of the maximum frequency encountered.\n int maxFreq = 0;\n\n // Iterate through the counter to find the maximum frequency.\n for (auto& [key, val] : counter) {\n maxFreq = max(maxFreq, val);\n }\n \n // Create a vector to store the mode(s), which are the values with maximum frequency.\n vector ans;\n\n // Iterate through the counter again to find the values with maximum frequency and add them to the \'ans\' vector.\n for (auto& [key, val] : counter) {\n if (val == maxFreq) {\n ans.push_back(key);\n } \n }\n \n // Return the \'ans\' vector containing the mode(s) of the BST.\n return ans;\n }\n};\n\n```\n\n\n```C []\n\n#include \n#include \n\nstruct TreeNode {\n int val;\n struct TreeNode *left;\n struct TreeNode *right;\n};\n\nstruct TreeNode* createNode(int val) {\n struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n node->val = val;\n node->left = NULL;\n node->right = NULL;\n return node;\n}\n\nstruct ModeResult {\n int* modes;\n int count;\n};\n\nvoid push(struct TreeNode** stack, int* top, struct TreeNode* node) {\n (*top)++;\n stack[*top] = node;\n}\n\nstruct TreeNode* pop(struct TreeNode** stack, int* top) {\n struct TreeNode* node = stack[*top];\n (*top)--;\n return node;\n}\n\nstruct ModeResult findMode(struct TreeNode* root) {\n struct ModeResult result;\n result.modes = NULL;\n result.count = 0;\n\n if (root == NULL) {\n return result;\n }\n\n int* counter = (int*)calloc(1000, sizeof(int)); // Assuming values are within the range of 0 to 999\n\n struct TreeNode* stack[1000]; // Stack for iterative traversal\n int top = -1; // Top of the stack\n\n push(stack, &top, root);\n\n while (top >= 0) {\n struct TreeNode* node = pop(stack, &top);\n counter[node->val]++;\n\n if (node->left != NULL) {\n push(stack, &top, node->left);\n }\n if (node->right != NULL) {\n push(stack, &top, node->right);\n }\n }\n\n int maxFreq = 0;\n for (int i = 0; i < 1000; i++) {\n maxFreq = maxFreq > counter[i] ? maxFreq : counter[i];\n }\n\n int* ans = (int*)malloc(maxFreq * sizeof(int));\n int ansCount = 0;\n for (int i = 0; i < 1000; i++) {\n if (counter[i] == maxFreq) {\n ans[ansCount++] = i;\n }\n }\n\n free(counter);\n\n result.modes = ans;\n result.count = ansCount;\n return result;\n}\n\n\n```\n\n```Java []\nclass Solution {\n public int[] findMode(TreeNode root) {\n Map counter = new HashMap();\n Stack stack = new Stack();\n stack.push(root);\n \n while (!stack.empty()) {\n TreeNode node = stack.pop();\n \n counter.put(node.val, counter.getOrDefault(node.val, 0) + 1);\n if (node.left != null) {\n stack.push(node.left);\n }\n if (node.right != null) {\n stack.push(node.right);\n }\n }\n \n \n int maxFreq = 0;\n for (int key : counter.keySet()) {\n maxFreq = Math.max(maxFreq, counter.get(key));\n }\n \n List ans = new ArrayList();\n for (int key : counter.keySet()) {\n if (counter.get(key) == maxFreq) {\n ans.add(key);\n }\n }\n \n int[] result = new int[ans.size()];\n for (int i = 0; i < ans.size(); i++) {\n result[i] = ans.get(i);\n }\n \n return result;\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def findMode(self, root: Optional[TreeNode]) -> List[int]:\n counter = defaultdict(int)\n stack = [root]\n \n while stack:\n node = stack.pop()\n counter[node.val] += 1\n \n if node.left:\n stack.append(node.left)\n if node.right:\n stack.append(node.right)\n \n max_freq = max(counter.values())\n \n ans = []\n for key in counter:\n if counter[key] == max_freq:\n ans.append(key)\n \n return ans\n\n```\n\n```javascript []\nclass TreeNode {\n constructor(val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n}\n\nclass Solution {\n findMode(root) {\n const counter = new Array(1000).fill(0); // Assuming values are within the range of 0 to 999\n\n const stack = [];\n stack.push(root);\n\n while (stack.length > 0) {\n const node = stack.pop();\n\n counter[node.val]++;\n\n if (node.left) {\n stack.push(node.left);\n }\n if (node.right) {\n stack.push(node.right);\n }\n }\n\n let maxFreq = 0;\n for (let i = 0; i < 1000; i++) {\n maxFreq = Math.max(maxFreq, counter[i]);\n }\n\n const ans = [];\n for (let i = 0; i < 1000; i++) {\n if (counter[i] === maxFreq) {\n ans.push(i);\n }\n }\n\n return ans;\n }\n}\n\n\n```\n\n---\n#### **Approach 3(BFS)**\n1. The findMode function is designed to find the mode(s) of a binary search tree (BST) using a level-order traversal. It employs a queue to perform the traversal.\n\n1. An unordered map called counter is used to store the frequency of values encountered in the BST. Each value is used as a key, and its frequency as the corresponding value.\n\n1. A queue named queue is created to facilitate level-order tree traversal. Initially, it is loaded with the root of the tree.\n\n1. The code enters a loop to perform level-order tree traversal while the queue is not empty. It processes nodes level by level, from left to right.\n\n1. For each node, it increments the frequency counter in the counter map for the node\'s value.\n\n1. If the current node has a left child, it is pushed onto the queue for later processing.\n\n1. If the current node has a right child, it is also pushed onto the queue for later processing.\n\n1. After completing the traversal, it calculates the maximum frequency encountered in the counter map.\n\n1. A vector ans is created to store the mode(s), which are the values with the maximum frequency.\n\n1. The code iterates through the counter map again to find the values with the maximum frequency and adds them to the ans vector.\n\n1. Finally, the function returns the ans vector containing the mode(s) of the BST.\n\n# Complexity\n- Time complexity:\n $$O(n)$$\n \n\n- Space complexity:\n $$O(n)$$\n \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n // Function to find the mode(s) of a binary search tree (BST) using a level-order traversal.\n vector findMode(TreeNode* root) {\n // Create an unordered map to store the frequency of each value encountered in the BST.\n unordered_map counter;\n \n // Create a queue to facilitate level-order tree traversal.\n queue queue;\n queue.push(root);\n \n // Perform level-order tree traversal using a queue.\n while (!queue.empty()) {\n TreeNode* node = queue.front();\n queue.pop();\n\n // Increment the frequency counter for the current node\'s value.\n counter[node->val]++;\n\n // If the current node has a left child, push it onto the queue for later processing.\n if (node->left != nullptr) {\n queue.push(node->left);\n }\n\n // If the current node has a right child, push it onto the queue for later processing.\n if (node->right != nullptr) {\n queue.push(node->right);\n }\n }\n \n // Initialize a variable to keep track of the maximum frequency encountered.\n int maxFreq = 0;\n\n // Iterate through the counter to find the maximum frequency.\n for (auto& [key, val] : counter) {\n maxFreq = max(maxFreq, val);\n }\n \n // Create a vector to store the mode(s), which are the values with maximum frequency.\n vector ans;\n\n // Iterate through the counter again to find the values with maximum frequency and add them to the \'ans\' vector.\n for (auto& [key, val] : counter) {\n if (val == maxFreq) {\n ans.push_back(key);\n } \n }\n \n // Return the \'ans\' vector containing the mode(s) of the BST.\n return ans;\n }\n};\n\n\n\n```\n\n```C []\n\n\nstruct TreeNode {\n int val;\n struct TreeNode *left;\n struct TreeNode *right;\n};\n\nstruct TreeNode* createNode(int val) {\n struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n node->val = val;\n node->left = NULL;\n node->right = NULL;\n return node;\n}\n\nstruct ModeResult {\n int* modes;\n int count;\n};\n\nvoid enqueue(struct TreeNode** queue, int* front, int* rear, struct TreeNode* node) {\n if (*rear == 999) {\n return;\n }\n (*rear)++;\n queue[*rear] = node;\n}\n\nstruct TreeNode* dequeue(struct TreeNode** queue, int* front, int* rear) {\n if (*front == *rear) {\n return NULL;\n }\n (*front)++;\n return queue[*front];\n}\n\nstruct ModeResult findMode(struct TreeNode* root) {\n struct ModeResult result;\n result.modes = NULL;\n result.count = 0;\n\n if (root == NULL) {\n return result;\n }\n\n int counter[1000] = {0}; // Assuming values are within the range of 0 to 999\n\n struct TreeNode* queue[1000]; // Queue for level-order traversal\n int front = -1; // Front of the queue\n int rear = -1; // Rear of the queue\n\n enqueue(queue, &front, &rear, root);\n\n while (front != rear) {\n struct TreeNode* node = dequeue(queue, &front, &rear);\n\n counter[node->val]++;\n\n if (node->left != NULL) {\n enqueue(queue, &front, &rear, node->left);\n }\n if (node->right != NULL) {\n enqueue(queue, &front, &rear, node->right);\n }\n }\n\n int maxFreq = 0;\n for (int i = 0; i < 1000; i++) {\n maxFreq = maxFreq > counter[i] ? maxFreq : counter[i];\n }\n\n int* ans = (int*)malloc(maxFreq * sizeof(int));\n int ansCount = 0;\n for (int i = 0; i < 1000; i++) {\n if (counter[i] == maxFreq) {\n ans[ansCount++] = i;\n }\n }\n\n result.modes = ans;\n result.count = ansCount;\n return result;\n}\n\n\n\n```\n\n```Java []\nclass Solution {\n public int[] findMode(TreeNode root) {\n Map counter = new HashMap();\n Queue queue = new LinkedList();\n queue.add(root);\n \n while (!queue.isEmpty()) {\n TreeNode node = queue.remove();\n \n counter.put(node.val, counter.getOrDefault(node.val, 0) + 1);\n if (node.left != null) {\n queue.add(node.left);\n }\n if (node.right != null) {\n queue.add(node.right);\n }\n }\n \n int maxFreq = 0;\n for (int key : counter.keySet()) {\n maxFreq = Math.max(maxFreq, counter.get(key));\n }\n \n List ans = new ArrayList();\n for (int key : counter.keySet()) {\n if (counter.get(key) == maxFreq) {\n ans.add(key);\n }\n }\n \n int[] result = new int[ans.size()];\n for (int i = 0; i < ans.size(); i++) {\n result[i] = ans.get(i);\n }\n \n return result;\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def findMode(self, root: Optional[TreeNode]) -> List[int]:\n counter = defaultdict(int)\n queue = deque([root])\n \n while queue:\n node = queue.popleft()\n counter[node.val] += 1\n \n if node.left:\n queue.append(node.left)\n if node.right:\n queue.append(node.right)\n \n max_freq = max(counter.values())\n \n ans = []\n for key in counter:\n if counter[key] == max_freq:\n ans.append(key)\n \n return ans\n\n\n```\n```javascript []\nclass TreeNode {\n constructor(val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n}\n\nclass Solution {\n findMode(root) {\n const counter = new Array(1000).fill(0); // Assuming values are within the range of 0 to 999\n\n const queue = [];\n let front = 0;\n let rear = -1;\n\n if (root) {\n queue.push(root);\n rear++;\n }\n\n while (front <= rear) {\n const node = queue[front];\n front++;\n\n counter[node.val]++;\n\n if (node.left) {\n queue.push(node.left);\n rear++;\n }\n if (node.right) {\n queue.push(node.right);\n rear++;\n }\n }\n\n let maxFreq = 0;\n for (let i = 0; i < 1000; i++) {\n maxFreq = Math.max(maxFreq, counter[i]);\n }\n\n const ans = [];\n for (let i = 0; i < 1000; i++) {\n if (counter[i] === maxFreq) {\n ans.push(i);\n }\n }\n\n return ans;\n }\n}\n\n```\n\n\n---\n#### **Approach 4(No Hash Maps)**\n1. The findMode function is designed to find the mode(s) of a binary search tree (BST) using in-order traversal. In in-order traversal, nodes are visited in sorted order.\n\n1. A vector called values is initialized to store the values of the BST in sorted order.\n\n1. The dfs (Depth-First Search) function is called to perform an in-order traversal of the BST, populating the values vector with the values of the BST in sorted order.\n\n1. The code then initializes variables for tracking the maximum streak count, the current streak count, the current number being counted, and a vector to store the mode(s).\n\n1. It iterates through the values vector to count the occurrences of each number.\n\n1. If the current number is the same as the previous number, the current streak count is incremented.\n\n1. If the current number is different from the previous number, the current streak count is reset to 1, and the current number is updated.\n\n1. If the current streak count exceeds the maximum streak count, the ans vector is cleared, and the maximum streak count is updated.\n\n1. If the current streak matches the maximum streak, the current number is added to the ans vector.\n\n1. Finally, the function returns the ans vector, which contains the mode(s) of the BST, representing the numbers with the highest frequency in the BST.\n\n# Complexity\n- Time complexity:\n $$O(n)$$\n \n\n- Space complexity:\n $$O(n)$$\n \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n // Function to find the mode(s) of a binary search tree (BST) using in-order traversal.\n vector findMode(TreeNode* root) {\n vector values; // Initialize a vector to store the values of the BST in sorted order.\n dfs(root, values); // Perform an in-order traversal of the BST to populate the \'values\' vector.\n \n int maxStreak = 0; // Initialize the maximum streak count for the modes.\n int currStreak = 0; // Initialize the current streak count for the current number.\n int currNum = 0; // Initialize the current number being counted.\n vector ans; // Initialize a vector to store the mode(s).\n \n for (int num : values) {\n if (num == currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n \n if (currStreak > maxStreak) {\n ans = {}; // If a new maximum streak is found, clear the \'ans\' vector.\n maxStreak = currStreak; // Update the maximum streak count.\n }\n \n if (currStreak == maxStreak) {\n ans.push_back(num); // If the current streak matches the maximum streak, add the number to the \'ans\' vector.\n }\n }\n \n return ans; // Return the \'ans\' vector containing the mode(s) of the BST.\n }\n \n // Helper function for in-order traversal to populate the \'values\' vector.\n void dfs(TreeNode* node, vector& values) {\n if (node == nullptr) {\n return;\n }\n \n // In-order traversal visits nodes in sorted order: left, current, right.\n dfs(node->left, values); // Traverse the left subtree.\n values.push_back(node->val); // Add the current node\'s value to the \'values\' vector.\n dfs(node->right, values); // Traverse the right subtree.\n }\n};\n\n```\n\n\n```C []\n\n\nstruct TreeNode {\n int val;\n struct TreeNode *left;\n struct TreeNode *right;\n};\n\nstruct TreeNode* createNode(int val) {\n struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n node->val = val;\n node->left = NULL;\n node->right = NULL;\n return node;\n}\n\nstruct ModeResult {\n int* modes;\n int count;\n};\n\nvoid dfs(struct TreeNode* node, int* values, int* index) {\n if (node == NULL) {\n return;\n }\n\n // In-order traversal visits nodes in sorted order: left, current, right.\n dfs(node->left, values, index);\n values[(*index)++] = node->val;\n dfs(node->right, values, index);\n}\n\nstruct ModeResult findMode(struct TreeNode* root) {\n struct ModeResult result;\n result.modes = NULL;\n result.count = 0;\n\n if (root == NULL) {\n return result;\n }\n\n int values[1000]; // Assuming a maximum of 1000 values\n int index = 0;\n dfs(root, values, &index);\n\n int maxStreak = 0;\n int currStreak = 0;\n int currNum = 0;\n\n int ans[1000]; // Assuming a maximum of 1000 modes\n int ansCount = 0;\n\n for (int i = 0; i < index; i++) {\n int num = values[i];\n if (num == currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n\n if (currStreak > maxStreak) {\n ansCount = 0;\n maxStreak = currStreak;\n }\n\n if (currStreak == maxStreak) {\n ans[ansCount++] = num;\n }\n }\n\n int* finalAns = (int*)malloc(ansCount * sizeof(int));\n for (int i = 0; i < ansCount; i++) {\n finalAns[i] = ans[i];\n }\n\n result.modes = finalAns;\n result.count = ansCount;\n return result;\n}\n\n\n\n```\n\n```Java []\nclass Solution {\n public int[] findMode(TreeNode root) {\n List values = new ArrayList();\n dfs(root, values);\n\n int maxStreak = 0;\n int currStreak = 0;\n int currNum = 0;\n List ans = new ArrayList();\n\n for (int num : values) {\n if (num == currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n \n if (currStreak > maxStreak) {\n ans = new ArrayList();\n maxStreak = currStreak;\n }\n \n if (currStreak == maxStreak) {\n ans.add(num);\n }\n }\n \n int[] result = new int[ans.size()];\n for (int i = 0; i < ans.size(); i++) {\n result[i] = ans.get(i);\n }\n \n return result;\n }\n \n public void dfs(TreeNode node, List values) {\n if (node == null) {\n return;\n }\n \n // Inorder traversal visits nodes in sorted order\n dfs(node.left, values);\n values.add(node.val);\n dfs(node.right, values);\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def findMode(self, root: Optional[TreeNode]) -> List[int]:\n def dfs(node, values):\n if not node:\n return\n \n # Inorder traversal visits nodes in sorted order\n dfs(node.left, values)\n values.append(node.val)\n dfs(node.right, values)\n \n values = []\n dfs(root, values)\n \n max_streak = 0\n curr_streak = 0\n curr_num = 0\n ans = []\n \n for num in values:\n if num == curr_num:\n curr_streak += 1\n else:\n curr_streak = 1\n curr_num = num\n \n if curr_streak > max_streak:\n ans = []\n max_streak = curr_streak\n\n if curr_streak == max_streak:\n ans.append(num)\n\n return ans\n\n\n```\n```javascript []\n\nclass TreeNode {\n constructor(val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n}\n\nclass Solution {\n findMode(root) {\n const values = [];\n\n function dfs(node) {\n if (node) {\n // In-order traversal visits nodes in sorted order: left, current, right.\n dfs(node.left);\n values.push(node.val);\n dfs(node.right);\n }\n }\n\n dfs(root);\n\n let maxStreak = 0;\n let currStreak = 0;\n let currNum = 0;\n const ans = [];\n\n for (let num of values) {\n if (num === currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n\n if (currStreak > maxStreak) {\n ans.length = 0;\n maxStreak = currStreak;\n }\n\n if (currStreak === maxStreak) {\n ans.push(num);\n }\n }\n\n return ans;\n }\n}\n\n```\n\n---\n#### **Approach 5(No "Values" array)**\n1. The findMode function is designed to find the mode(s) of a binary search tree (BST) using a depth-first search (DFS). It initializes data structures to keep track of mode-related information.\n\n1. The ans vector is used to store the mode(s), maxStreak tracks the maximum streak count, currStreak tracks the current streak count, and currNum keeps track of the current number being counted.\n\n1. The dfs function is a helper function for DFS traversal of the BST. It processes nodes in an in-order manner, as it first traverses the left subtree, then the current node, and finally the right subtree.\n\n1. If the current node is nullptr (null), the function returns, effectively handling the base case of the recursion.\n\n1. Within the dfs function, the code processes the left subtree recursively.\n\n1. It counts the frequency of each number and determines the mode(s) by tracking streaks of numbers. If the current number is the same as the previous one, the current streak count is incremented. If the current number is different, the current streak count is reset to 1, and the current number is updated.\n\n1. If the current streak count is greater than the maximum streak count encountered so far, the ans vector is cleared (set to an empty vector), and the maximum streak count is updated.\n\n1. If the current streak count matches the maximum streak count, the current number is added to the ans vector.\n\n1. After processing the left subtree and current node, the code recursively processes the right subtree.\n\n1. The findMode function calls dfs to perform the traversal, and after traversal is complete, it returns the ans vector, which contains the mode(s) of the BST. The modes represent the numbers with the highest frequency in the BST.\n\n# Complexity\n- Time complexity:\n $$O(n)$$\n \n\n- Space complexity:\n $$O(n)$$\n \n\n\n# Code\n```C++ []\nclass Solution {\npublic:\n vector ans; // Initialize a vector to store the mode(s).\n int maxStreak = 0; // Initialize the maximum streak count for the modes.\n int currStreak = 0; // Initialize the current streak count for the current number.\n int currNum = 0; // Initialize the current number being counted.\n \n vector findMode(TreeNode* root) {\n dfs(root); // Perform a depth-first search (DFS) to populate the \'ans\' vector with modes.\n return ans; // Return the \'ans\' vector containing the mode(s).\n }\n \n // Helper function for DFS to traverse the binary search tree.\n void dfs(TreeNode* node) {\n if (node == nullptr) {\n return;\n }\n\n dfs(node->left); // Recursively traverse the left subtree.\n \n int num = node->val;\n if (num == currNum) {\n currStreak++; // Increment the current streak count if the current number matches the previous number.\n } else {\n currStreak = 1; // Reset the current streak count to 1 if the number is different.\n currNum = num; // Update the current number.\n }\n\n if (currStreak > maxStreak) {\n ans = {}; // If a new maximum streak is found, clear the \'ans\' vector.\n maxStreak = currStreak; // Update the maximum streak count.\n }\n\n if (currStreak == maxStreak) {\n ans.push_back(num); // If the current streak matches the maximum streak, add the number to the \'ans\' vector.\n }\n\n dfs(node->right); // Recursively traverse the right subtree.\n }\n};\n\n\n```\n\n```C []\n\n\n\nstruct TreeNode {\n int val;\n struct TreeNode *left;\n struct TreeNode *right;\n};\n\nstruct TreeNode* createNode(int val) {\n struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n node->val = val;\n node->left = NULL;\n node->right = NULL;\n return node;\n}\n\nstruct ModeResult {\n int* modes;\n int count;\n};\n\nvoid dfs(struct TreeNode* node, int* ans, int* maxStreak, int* currStreak, int* currNum) {\n if (node == NULL) {\n return;\n }\n\n dfs(node->left, ans, maxStreak, currStreak, currNum);\n\n int num = node->val;\n if (num == *currNum) {\n (*currStreak)++;\n } else {\n (*currStreak) = 1;\n (*currNum) = num;\n }\n\n if (*currStreak > *maxStreak) {\n (*maxStreak) = (*currStreak);\n (*ans) = 0; // Clear the \'ans\' vector by setting it to zero.\n }\n\n if (*currStreak == *maxStreak) {\n (*ans)++;\n }\n\n dfs(node->right, ans, maxStreak, currStreak, currNum);\n}\n\nstruct ModeResult findMode(struct TreeNode* root) {\n struct ModeResult result;\n result.modes = NULL;\n result.count = 0;\n\n if (root == NULL) {\n return result;\n }\n\n int maxStreak = 0;\n int currStreak = 0;\n int currNum = INT_MIN;\n\n int ans = 0;\n\n dfs(root, &ans, &maxStreak, &currStreak, &currNum);\n\n int* finalAns = (int*)malloc(ans * sizeof(int));\n\n for (int i = 0; i < ans; i++) {\n finalAns[i] = maxStreak;\n }\n\n result.modes = finalAns;\n result.count = ans;\n\n return result;\n}\n\n\n\n```\n```Java []\nclass Solution {\n int maxStreak = 0;\n int currStreak = 0;\n int currNum = 0;\n List ans = new ArrayList();\n \n public int[] findMode(TreeNode root) {\n dfs(root);\n \n int[] result = new int[ans.size()];\n for (int i = 0; i < ans.size(); i++) {\n result[i] = ans.get(i);\n }\n \n return result;\n }\n \n public void dfs(TreeNode node) {\n if (node == null) {\n return;\n }\n \n dfs(node.left);\n int num = node.val;\n if (num == currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n\n if (currStreak > maxStreak) {\n ans = new ArrayList();\n maxStreak = currStreak;\n }\n\n if (currStreak == maxStreak) {\n ans.add(num);\n }\n \n dfs(node.right);\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def findMode(self, root: Optional[TreeNode]) -> List[int]:\n def dfs(node):\n nonlocal max_streak, curr_streak, curr_num, ans\n if not node:\n return\n \n dfs(node.left)\n \n num = node.val\n if num == curr_num:\n curr_streak += 1\n else:\n curr_streak = 1\n curr_num = num\n\n if curr_streak > max_streak:\n ans = []\n max_streak = curr_streak\n\n if curr_streak == max_streak:\n ans.append(num)\n \n dfs(node.right)\n\n max_streak = 0\n curr_streak = 0\n curr_num = 0\n ans = []\n dfs(root)\n return ans\n\n\n```\n```javascript []\n\nclass TreeNode {\n constructor(val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n}\n\nclass Solution {\n findMode(root) {\n const ans = [];\n let maxStreak = 0;\n let currStreak = 0;\n let currNum = 0;\n\n function dfs(node) {\n if (node) {\n dfs(node.left);\n\n const num = node.val;\n if (num === currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n\n if (currStreak > maxStreak) {\n maxStreak = currStreak;\n ans.length = 0;\n }\n\n if (currStreak === maxStreak) {\n ans.push(num);\n }\n\n dfs(node.right);\n }\n }\n\n dfs(root);\n\n return ans;\n }\n}\n\n```\n\n---\n#### **Approach 6(Morris Traversal)**\n1. The findMode function is designed to find the mode(s) of a binary search tree using Morris Traversal, a space-efficient in-order traversal method. It initializes data structures to keep track of mode-related information.\n\n1. The ans vector is used to store the mode(s), maxStreak tracks the maximum streak count, currStreak tracks the current streak count, and currNum keeps track of the current number being counted.\n\n1. A pointer curr is initialized to the root of the binary search tree, allowing traversal.\n\n1. The while loop iterates until curr is not nullptr, meaning all nodes have been visited.\n\n1. If the current node curr has a left child, the algorithm enters a Morris Traversal section. It finds the rightmost node in the left subtree, which is often referred to as the "friend" in Morris Traversal, and establishes a temporary link from this node to the current node.\n\n1. The temporary link helps the traversal algorithm remember where to return after processing the left subtree. It is crucial to delete the temporary link after using it to avoid infinite loops.\n\n1. After processing the left subtree, the algorithm reaches the "else" section, where it handles the current node. It checks the number and updates the streak counts accordingly.\n\n1. If a new maximum streak is found, the ans vector is cleared (set to an empty vector), and the maximum streak count is updated.\n\n1. If the current streak matches the maximum streak, the current number is added to the ans vector.\n\n1. The algorithm then moves to the right subtree and continues the traversal process.\n\n1. Once all nodes have been visited, the ans vector contains the mode(s) of the BST.\n\n# Complexity\n- Time complexity:\n $$O(n)$$\n \n\n- Space complexity:\n $$O(1)$$\n \n\n\n# Code\n```C++ []\n\nclass Solution {\npublic: \n vector findMode(TreeNode* root) {\n vector ans; // Initialize a vector to store the mode(s).\n int maxStreak = 0; // Initialize the maximum streak count for the modes.\n int currStreak = 0; // Initialize the current streak count for the current number.\n int currNum = 0; // Initialize the current number being counted.\n \n TreeNode* curr = root; // Initialize a pointer to the current node and set it to the root.\n \n while (curr != nullptr) {\n if (curr->left != nullptr) {\n // Find the "friend" (the rightmost node in the left subtree) and establish a temporary link.\n TreeNode* friendNode = curr->left;\n while (friendNode->right != nullptr) {\n friendNode = friendNode->right;\n }\n \n friendNode->right = curr; // Temporary link from friendNode to curr.\n \n // Delete the edge after using it to prevent infinite loops (Morris Traversal).\n TreeNode* left = curr->left;\n curr->left = nullptr;\n curr = left; // Move to the left subtree.\n } else {\n // Handle the current node in Morris Traversal.\n int num = curr->val;\n if (num == currNum) {\n currStreak++; // Increment the current streak count if the current number matches the previous number.\n } else {\n currStreak = 1; // Reset the current streak count to 1 if the number is different.\n currNum = num; // Update the current number.\n }\n\n if (currStreak > maxStreak) {\n ans = {}; // If a new maximum streak is found, clear the \'ans\' vector.\n maxStreak = currStreak; // Update the maximum streak count.\n }\n\n if (currStreak == maxStreak) {\n ans.push_back(num); // If the current streak matches the maximum streak, add the number to the \'ans\' vector.\n }\n \n curr = curr->right; // Move to the right subtree.\n }\n }\n \n return ans; // Return the \'ans\' vector containing the mode(s).\n }\n};\n\n```\n\n```C []\n#include \n#include \n\nstruct TreeNode {\n int val;\n struct TreeNode *left;\n struct TreeNode *right;\n};\n\nstruct TreeNode* createNode(int val) {\n struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));\n node->val = val;\n node->left = NULL;\n node->right = NULL;\n return node;\n}\n\nstruct ModeResult {\n int* modes;\n int count;\n};\n\nvoid findMode(struct TreeNode* root, struct ModeResult* result) {\n result->modes = NULL;\n result->count = 0;\n\n if (root == NULL) {\n return;\n }\n\n struct TreeNode* curr = root;\n struct TreeNode* friendNode = NULL;\n int maxStreak = 0;\n int currStreak = 0;\n int currNum = 0;\n\n while (curr != NULL) {\n if (curr->left != NULL) {\n friendNode = curr->left;\n while (friendNode->right != NULL && friendNode->right != curr) {\n friendNode = friendNode->right;\n }\n\n if (friendNode->right == NULL) {\n friendNode->right = curr;\n curr = curr->left;\n } else {\n friendNode->right = NULL;\n\n int num = curr->val;\n if (num == currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n\n if (currStreak > maxStreak) {\n maxStreak = currStreak;\n result->count = 0;\n }\n\n if (currStreak == maxStreak) {\n result->count++;\n result->modes = (int*)realloc(result->modes, result->count * sizeof(int));\n result->modes[result->count - 1] = num;\n }\n\n curr = curr->right;\n }\n } else {\n int num = curr->val;\n if (num == currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n\n if (currStreak > maxStreak) {\n maxStreak = currStreak;\n result->count = 0;\n }\n\n if (currStreak == maxStreak) {\n result->count++;\n result->modes = (int*)realloc(result->modes, result->count * sizeof(int));\n result->modes[result->count - 1] = num;\n }\n\n curr = curr->right;\n }\n }\n}\n\n\n\n```\n\n```Java []\nclass Solution {\n public int[] findMode(TreeNode root) {\n int maxStreak = 0;\n int currStreak = 0;\n int currNum = 0;\n List ans = new ArrayList();\n \n TreeNode curr = root;\n while (curr != null) {\n if (curr.left != null) {\n // Find the friend\n TreeNode friend = curr.left;\n while (friend.right != null) {\n friend = friend.right;\n }\n \n friend.right = curr;\n \n // Delete the edge after using it\n TreeNode left = curr.left;\n curr.left = null;\n curr = left;\n } else {\n // Handle the current node\n int num = curr.val;\n if (num == currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n\n if (currStreak > maxStreak) {\n ans = new ArrayList();\n maxStreak = currStreak;\n }\n\n if (currStreak == maxStreak) {\n ans.add(num);\n }\n \n curr = curr.right;\n }\n }\n \n \n int[] result = new int[ans.size()];\n for (int i = 0; i < ans.size(); i++) {\n result[i] = ans.get(i);\n }\n \n return result;\n }\n}\n\n```\n\n```python3 []\nclass Solution:\n def findMode(self, root: Optional[TreeNode]) -> List[int]:\n max_streak = 0\n curr_streak = 0\n curr_num = 0\n ans = []\n \n curr = root\n while curr:\n if curr.left:\n # Find the friend\n friend = curr.left\n while friend.right:\n friend = friend.right\n \n friend.right = curr\n \n # Delete the edge after using it\n left = curr.left\n curr.left = None\n curr = left\n else:\n # Handle the current node\n num = curr.val\n if num == curr_num:\n curr_streak += 1\n else:\n curr_streak = 1\n curr_num = num\n\n if curr_streak > max_streak:\n ans = []\n max_streak = curr_streak\n\n if curr_streak == max_streak:\n ans.append(num)\n \n curr = curr.right\n \n return ans\n\n```\n\n```javascript []\nclass TreeNode {\n constructor(val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n}\n\nclass ModeResult {\n constructor() {\n this.modes = [];\n this.count = 0;\n }\n}\n\nfunction findMode(root) {\n const result = new ModeResult();\n\n if (root === null) {\n return result;\n }\n\n let curr = root;\n let friendNode = null;\n let maxStreak = 0;\n let currStreak = 0;\n let currNum = 0;\n\n while (curr !== null) {\n if (curr.left !== null) {\n friendNode = curr.left;\n while (friendNode.right !== null && friendNode.right !== curr) {\n friendNode = friendNode.right;\n }\n\n if (friendNode.right === null) {\n friendNode.right = curr;\n curr = curr.left;\n } else {\n friendNode.right = null;\n\n const num = curr.val;\n if (num === currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n\n if (currStreak > maxStreak) {\n maxStreak = currStreak;\n result.count = 0;\n }\n\n if (currStreak === maxStreak) {\n result.count++;\n result.modes.push(num);\n }\n\n curr = curr.right;\n }\n } else {\n const num = curr.val;\n if (num === currNum) {\n currStreak++;\n } else {\n currStreak = 1;\n currNum = num;\n }\n\n if (currStreak > maxStreak) {\n maxStreak = currStreak;\n result.count = 0;\n }\n\n if (currStreak === maxStreak) {\n result.count++;\n result.modes.push(num);\n }\n\n curr = curr.right;\n }\n }\n\n return result;\n}\n\n\n```\n\n---\n\n\n\n# PLEASE UPVOTE IF IT HELPED\n\n---\n---\n\n\n---

Find Mode in Binary Search Tree

Problem Description

Problem Description

Answer Panel