501. Find Mode in Binary Search Tree

Given a binary search tree (BST) with duplicates, find all themode(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],

   1
    \
     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).

Analysis:

If we in order traverse this type of tree, we can get a ascending order array of integer. The question becomes "how to record most frequent numbers"" in a sorted array.

The answer to that is: having a list/set to store most frequent numbers, a int maxf to store max frequency so far.

Keep scaning, when value is the same, we increment current frequency curf. when value changes, we do following:

1. if curf == maxf --> we add this number into return list
2. if curf > maxf --> clear returnlist, update maxf = curf, add this number to return list
3. if curf < maxf --> clear curf and move on.

Complexity:

Time: O(N) since its just traversing all element in tree once.

Space: O(logn) just the recursive stack space, which is the height of the tree.

Code:

//Code here
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    int maxf = 0, curf = 0;
    int curv = 0;
    List<Integer> returnList = new LinkedList<Integer>();

    public int[] findMode(TreeNode root) {
        if(root == null)
        {
            return new int[0];
        }
        curv = root.val;
        iot(root);
        update();

        int[] arr = new int[returnList.size()];
        int index = 0;
        for(Integer itr : returnList)
        {
            arr[index++] = itr;
        }
        return arr;
    }

    private void iot(TreeNode root)
    {
        if(root == null)
        {
            return;
        }
        iot(root.left);
        if(root.val == curv)
        {
            curf++;
        }
        else
        {
            update();
            curv = root.val;
            curf = 1;
        }
        iot(root.right);
    }

    private void update()
    {
        if(curf == maxf)
        {
            returnList.add(curv);
        }
        else if(curf > maxf)
        {
            maxf = curf;
            returnList.clear();
            returnList.add(curv);
        }
    }
}