Python solution with detailed explanation


  • 3
    G

    Solution

    Find Mode in Binary Search Tree https://leetcode.com/problems/find-mode-in-binary-search-tree/

    O(N) time & O(N) Space

    • Use a dictionary to store the frequency of each interger. Then simply find the largest frequency and return all the associated keys.
    • Note we do not use the property of BST in this solution.
    from collections import defaultdict
    class Solution(object):
        def helper(self, root, cache):
            if root == None:
                return
            cache[root.val] += 1
            self.helper(root.left, cache)
            self.helper(root.right, cache)
            return
        
        def findMode(self, root):
            """
            :type root: TreeNode
            :rtype: List[int]
            """
            if root == None:
                return []
            cache = defaultdict(int)
            self.helper(root, cache)
            max_freq = max(cache.values())
            result = [k for k,v in cache.items() if v == max_freq]
            return result
    

    O(N) time and O(1) Space

    Divide and Conquer

    • Mode lies entirely in left subtree, or in right subtree or the middle element is the mode.
    • Time would be NlogN at best and space O(1)

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.