## # 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
``````

Approach 1:

Approach 2: