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