Reference: LeetCode
Difficulty: Easy

## Problem

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.

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

Example:

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

## Analysis

Methods:

1. Hash Map
• In the inorder traversal, we do the counting work and use a hash map to store the values. In the meanwhile, we calculate the maxCount.
• Iterate the map and add those keys that satisfy the requirement.
• Convert List<Integer> to int[] in a for-loop.

Time: $O(N)$
Space: $O(N)$

1. Get Max First
• In the first traversal, calculate the maxCount, later we can add those integers to the list directly in the second traversal.

Time: $O(N)$
Space: $O(1)$

Comment
Junhao Wang
Hi, I was a master student at USC studying Computer Science.