# Leetcode – Find Mode in Binary Search Tree Solution in Python

## Introduction

Binary search trees (BSTs) are data structures that hold their elements in sorted order. They are used widely for efficient search, insertion, and deletion of elements. Leetcode offers various problems that help in honing the skills to manipulate and solve problems using BSTs. In this article, we will focus on one such problem: “Find Mode in Binary Search Tree”, and explore different approaches to solve it in Python.

The problem is described as:

Given a binary search tree (BST) with duplicates, find all the mode(s) (the most frequently occurring element) in the given BST.

The binary tree uses the following structure for nodes.

class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right

## Approach 1: Using Hash Map

The simplest approach is to traverse the entire tree and store the frequency of each element in a hash map. Once we have the frequencies, we can iterate through the hash map to find the maximum frequency and return all elements that have this frequency.

def findMode(root):
if not root:
return []

# Count the occurrences of each value
count = {}
def dfs(node):
if node:
count[node.val] = count.get(node.val, 0) + 1
dfs(node.left)
dfs(node.right)

# Perform DFS traversal to populate the count dictionary
dfs(root)

# Find the maximum frequency
max_freq = max(count.values())

# Return all elements that have the maximum frequency
return [key for key, value in count.items() if value == max_freq]

This approach uses O(N) space, where N is the number of nodes in the tree. It also takes O(N) time to traverse the tree.

## Approach 2: Using In-order Traversal

Since the tree is a BST, an in-order traversal will give us elements in sorted order. We can keep track of the current number, its count, the maximum frequency, and the modes while doing the in-order traversal. This allows us to solve the problem in O(1) extra space if we disregard the space needed for the output.

def findMode(root):
# Variables to keep track of the current number and count, max frequency and modes
current_number = current_count = max_count = 0
modes = []

# Helper function to handle the logic when a number is encountered
def handle_value(val):
nonlocal current_number, current_count, max_count, modes
if val != current_number:
current_number = val
current_count = 0
current_count += 1
if current_count > max_count:
max_count = current_count
modes = [current_number]
elif current_count == max_count:
modes.append(current_number)

# Perform in-order traversal
def inorder(node):
if node:
inorder(node.left)
handle_value(node.val)
inorder(node.right)

# Populate the modes list
inorder(root)

return modes

This approach takes O(N) time, but uses O(1) extra space (excluding the space for output).

## Approach 3: Morris In-order Traversal

We can optimize the space further using Morris In-order Traversal. This algorithm doesn’t use recursion or a stack for traversal, which makes it use constant extra space.

def findMode(root):
current_number = current_count = max_count = 0
modes = []

# Helper function to handle the logic when a number is encountered
def handle_value(val):
nonlocal current_number, current_count, max_count, modes
if val != current_number:
current_number = val
current_count = 0
current_count += 1
if current_count > max_count:
max_count = current_count
modes = [current_number]
elif current_count == max_count:
modes.append(current_number)

# Perform Morris In-order Traversal
current = root
while current:
if not current.left:
handle_value(current.val)
current = current.right
else:
# Find the inorder predecessor of current
pre = current.left
while pre.right and pre.right != current:
pre = pre.right
if not pre.right:
# Make current as the right child of its inorder predecessor
pre.right = current
current = current.left
else:
# Revert the changes made in the 'if' part to restore the original tree
pre.right = None
handle_value(current.val)
current = current.right

return modes

This approach takes O(N) time to traverse the tree but uses O(1) extra space (excluding the space for output).

## Conclusion

We’ve explored three different approaches to solving the “Find Mode in Binary Search Tree” problem on Leetcode using Python. The first approach utilized hash maps to store frequencies, the second used in-order traversal to save space, and the third optimized space further with Morris traversal. Depending on the constraints and requirements of the problem at hand, you can choose the approach that best suits the needs in terms of time and space complexity.