# 501. Find Mode in Binary Search Tree

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.

Example:

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

# Solution

Approach 1: an inorder traversal guarantees the results are ordered -- use recursion since recursion stack doesn't count in this problem.

Approach 2: to really use O(1) space, use Morrison traversal -- build a (partially) threaded BST where each node's right points to its inorder successor.

# Code (Python)

Approach 1:

    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.modes = []
        self.mode_count = 0
        self.current_val = - float('inf')
        self.current_count = 0
        
        self._traverse_inorder(root)
        
        return self.modes
    
    def _traverse_inorder(self, node):
        if not node:
            return
        if node.left:
            self._traverse_inorder(node.left)
        self._process_node(node)
        if node.right:
            self._traverse_inorder(node.right)
    
    def _process_node(self, node):
        if node.val == self.current_val:
            self.current_count += 1
        else:
            self.current_val = node.val
            self.current_count = 1
        if self.current_count == self.mode_count:
            self.modes.append(node.val)
        if self.current_count > self.mode_count:
            self.modes = [node.val]
            self.mode_count = self.current_count

Approach 2:

    def findMode(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        self.modes = []
        self.mode_count = 0
        self.current_val = - float('inf')
        self.current_count = 0
        
        self._traverse_inorder_morrison(root)
        
        return self.modes

    def _traverse_inorder_morrison(self, node):
        while node:
            if not node.left:
                self._process_node(node)
                node = node.right
            else:
                predecessor = node.left
                while predecessor.right and predecessor.right != node:
                    predecessor = predecessor.right
                if not predecessor.right:
                    predecessor.right = node
                    node = node.left
                else:
                    predecessor.right = None
                    self._process_node(node)
                    node = node.right

# Code (C++)

Approach 1:

Approach 2: