501 Find Mode in Binary Search Tree¶

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.

For example: Given BST [1,null,2,2],

return [2].

Note: If a tree has more than one mode, you can return them in any order.

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

Solution1: Recursion w/ extra space¶

Time complexity: O(n)

Space complexity: O(n)

// Running time: 8 ms
class Solution {
public:
  vector<int> findMode(TreeNode* root) {
    inorder(root);
    return ans_;
  }
private:
  int val_ = 0;
  int count_ = 0;
  int max_count_ = 0;
  vector<int> ans_;

  void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    visit(root->val);
    inorder(root->right);
  }

  void visit(int val) {
    if (count_ > 0 && val == val_) {
      ++count_;
    } else {
      val_ = val;
      count_ = 1;
    }

    if (count_ > max_count_) {
      max_count_ = count_;
      ans_.clear();
    }

    if (count_ == max_count_)
      ans_.push_back(val);
  }
};

Solution2: Recursion w/o extra space¶

Two passes. First pass to find the count of the mode, second pass to collect all the modes.

Time complexity: O(n)

Space complexity: O(1)

// Running time: 8 ms
class Solution {
public:
  vector<int> findMode(TreeNode* root) {
    inorder(root);
    mode_count_ = max_count_;
    count_ = 0;
    inorder(root);
    return ans_;
  }
private:
  int val_ = 0;
  int count_ = 0;
  int mode_count_ = INT_MAX;
  int max_count_ = 0;
  vector<int> ans_;

  void inorder(TreeNode* root) {
    if (root == nullptr) return;
    inorder(root->left);
    visit(root->val);
    inorder(root->right);
  }

  void visit(int val) {
    if (count_ > 0 && val == val_) {
      ++count_;
    } else {
      val_ = val;
      count_ = 1;
    }

    if (count_ > max_count_)
      max_count_ = count_;

    if (count_ == mode_count_)
      ans_.push_back(val);
  }
};