Find Mode in Binary Search Tree

Leave a comment

June 21, 2017 by oneOokay

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],

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


如果用hashmap的话是很简单,但是一个without using any extra space的解法挺有意思的. O(1).

我自己要注意的点就是:尽管这个是允许duplicates的 binary search tree,在树上看相同的值可能到处是,但是只要inorder traversal的输出,数字的大小就是按照顺序排列的.

O(1)的用了两次inorder traversal: 第一次得到modes的个数,然后新建那个int[] array.第二次inorder traversal fill in result array

public int[] findMode(TreeNode root) {
        inorder(root);
        modesRes = new int[modeCount];
        modeCount = 0;//reset modeCount;
        curCount = 0; //reset curCount;
        inorder(root);
        return modesRes;
    }
    private int currVal;
    private int curCount = 0;
    private int maxCount = 0;
    private int modeCount = 0;
    private int[] modesRes;
    
    private void handleValue(int value){
        if (value != currVal){
            currVal = value;
            curCount = 0;
        }
        curCount ++;
        if (curCount > maxCount){
            maxCount = curCount;
            modeCount = 1; //reset mode count
        }else if (curCount == maxCount){
            
            if (modesRes != null){
                modesRes[modeCount] = currVal;
            }
            modeCount ++;
        }
        
    }
    private void inorder(TreeNode node){
        if (node == null) return;
        inorder(node.left);
        handleValue(node.val);
        inorder(node.right);
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: