501. Find Mode in Binary Search Tree LeetCode Solution

In this guide, you will get 501. Find Mode in Binary Search Tree LeetCode Solution with the best time and space complexity. The solution to Find Mode in Binary Search Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Find Mode in Binary Search Tree solution in C++
4. Find Mode in Binary Search Tree solution in Java
5. Find Mode in Binary Search Tree solution in Python
6. Additional Resources

Problem Statement of Find Mode in Binary Search Tree

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.
If the tree has more than one mode, return them in any order.
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 1:

Input: root = [1,null,2,2]
Output: [2]

Example 2:

Input: root = [0]
Output: [0]

Constraints:

The number of nodes in the tree is in the range [1, 104].
-105 <= Node.val <= 105

Follow up: Could you do that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Complexity Analysis

• Time Complexity: O(n)
• Space Complexity: O(\log n)

501. Find Mode in Binary Search Tree LeetCode Solution in C++

class Solution {
 public:
  vector<int> findMode(TreeNode* root) {
    vector<int> ans;
    int count = 0;
    int maxCount = 0;

    inorder(root, count, maxCount, ans);
    return ans;
  }

 private:
  TreeNode* pred = nullptr;

  void inorder(TreeNode* root, int& count, int& maxCount, vector<int>& ans) {
    if (root == nullptr)
      return;

    inorder(root->left, count, maxCount, ans);
    updateCount(root, count, maxCount, ans);
    inorder(root->right, count, maxCount, ans);
  }

  void updateCount(TreeNode* root, int& count, int& maxCount,
                   vector<int>& ans) {
    if (pred && pred->val == root->val)
      ++count;
    else
      count = 1;

    if (count > maxCount) {
      maxCount = count;
      ans = {root->val};
    } else if (count == maxCount) {
      ans.push_back(root->val);
    }

    pred = root;
  }
};
/* code provided by PROGIEZ */

501. Find Mode in Binary Search Tree LeetCode Solution in Java

class Solution {
  public int[] findMode(TreeNode root) {
    List<Integer> ans = new ArrayList<>();
    // count[0] := currCount
    // count[1] := maxCount
    int[] count = new int[2];

    inorder(root, count, ans);
    return ans.stream().mapToInt(Integer::intValue).toArray();
  }

  private TreeNode pred = null;

  private void inorder(TreeNode root, int[] count, List<Integer> ans) {
    if (root == null)
      return;

    inorder(root.left, count, ans);
    updateCount(root, count, ans);
    inorder(root.right, count, ans);
  }

  private void updateCount(TreeNode root, int[] count, List<Integer> ans) {
    if (pred != null && pred.val == root.val)
      ++count[0];
    else
      count[0] = 1;

    if (count[0] > count[1]) {
      count[1] = count[0];
      ans.clear();
      ans.add(root.val);
    } else if (count[0] == count[1]) {
      ans.add(root.val);
    }

    pred = root;
  }
}
// code provided by PROGIEZ

501. Find Mode in Binary Search Tree LeetCode Solution in Python

class Solution:
  def findMode(self, root: TreeNode | None) -> list[int]:
    self.ans = []
    self.pred = None
    self.count = 0
    self.maxCount = 0

    def updateCount(root: TreeNode | None) -> None:
      if self.pred and self.pred.val == root.val:
        self.count += 1
      else:
        self.count = 1

      if self.count > self.maxCount:
        self.maxCount = self.count
        self.ans = [root.val]
      elif self.count == self.maxCount:
        self.ans.append(root.val)

      self.pred = root

    def inorder(root: TreeNode | None) -> None:
      if not root:
        return

      inorder(root.left)
      updateCount(root)
      inorder(root.right)

    inorder(root)
    return self.ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.