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.