Problem statement

https://leetcode.com/problems/find-mode-in-binary-search-tree/

Solution

Original question is quite simple, just traverse tree in any way: and keep counter for every value. Time and space complexity will be O(n).

If we want to have O(1) space (without implicit stack), than it is quite difficult problem: you need to pass your data twice: on first pass, use inorder traversal, where we just find number of mode elements and their frequency. On the second pass, we find all elements with desired frequency. Note, that here we have O(h) for implicit stack.

Complexity

It is O(n) for time and `O(h) for space.

Code

class Solution(object):
    def findMode(self, root):
        def inorder(root):
            if not root: return
            inorder(root.left)
            handle(root.val)
            inorder(root.right)
    
        def handle(v):
            if v != self.curItem: 
                self.curItem = v
                self.curCount = 0
            self.curCount += 1
            if self.curCount > self.maxCount:
                self.modeSize = 1
                self.maxCount = self.curCount
            elif self.curCount == self.maxCount:
                if self.flag: self.res.append(v)
        
        self.flag, self.maxCount, self.curCount, self.curItem = False, 0, 0, None
        inorder(root)
        self.res = []
        self.flag, self.curCount = True, 0
        inorder(root)
        return self.res

Remark

There is also Morris traversal, where it can be done in O(1) additional space.