501. Find Mode in Binary Search Tree

EasyTreeDepth-First SearchBinary Search TreeBinary Tree
Leetcode Link

Problem Description

The problem is about finding the most frequently occurring elements in a Binary Search Tree (BST). The challenge is that a BST may contain duplicates and the goal is to identify the mode(s), which are the values that appear most frequently. As a reminder, a BST has the property where each nodeโ€™s left child has a value less than or equal to its own value, while the right child has a value greater than or equal to its own value. This property must hold true for every nodeโ€™s left and right subtrees as well.

The output should be a list of the modes. If there's more than one mode, they can be returned in any order. What makes this interesting is that we must traverse the tree and keep track of the frequency of each element without knowing beforehand which values appear in the BST.

Intuition

To solve this problem, one effective approach is to perform an in-order traversal of the BST. An in-order traversal is a type of depth-first traversal that visits the left subtree, then the root node, and finally the right subtree. This traversal order guarantees that the values are accessed in a sorted manner because of the BST property.

As we perform the traversal, we can track the current value, its count, and compare it with the maximum frequency (or mode) encountered so far. There are a few edge cases to consider:

  • If the current value is the same as the previous value we saw, we increment the count for this value.
  • If it's a new value (not the same as the previous one), we reset the count to 1.
  • If the count for the current value is greater than the current maximum frequency, we update the maximum frequency and reset the list of modes to now only include this new value.
  • If the count matches the current maximum frequency, we add the current value to the list of modes.

A nonlocal variable is used to maintain state between recursive calls. Variables like mx (short for 'maximum'), prev (short for 'previous value'), ans (short for 'answer'), and cnt (short for 'count') are updated as the in-order traversal proceeds. After the traversal is complete, the ans list will contain the mode(s) of the BST.

This approach efficiently computes the mode(s) using the BST's inherent properties, all without needing additional data structures to track frequency of all elements, thus saving space.

Learn more about Tree, Depth-First Search, Binary Search Tree and Binary Tree patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Solution Approach

The solution uses a Depth-First Search (DFS) in-order traversal algorithm to walk through the tree. Since it's a BST, an in-order traversal will access the nodes in ascending order. This property is critical because it allows us to track the mode(s) without the need for additional data structures like a hash table to count the frequencies of each value.

In the Python solution, a nested function dfs is defined, capturing the variables mx, prev, ans, and cnt from the enclosing findMode function scope using the nonlocal keyword. These captured variables serve as state throughout the traversal:

  • mx: This keeps track of the maximum frequency of any value encountered so far.
  • prev: This holds the previous value processed in the in-order traversal. It's used to compare with the current node's value to determine if the count should be increased or reset.
  • cnt: This records the current count of consecutive nodes with the same value.
  • ans: This list stores the mode(s) โ€” the values with the highest frequency seen so far.

Here is a step-by-step explanation of the function dfs which is called with the root of the BST:

  • The base case checks if the current node root is None, and if it is, the function returns because there's nothing to process.
  • Recursive calls are made to visit the left subtree: dfs(root.left).
  • When control returns from the left subtree, the current node is processed. If prev is the same as root.val, cnt is incremented. Otherwise, cnt is set to 1 since we're seeing this value for the first time.
  • We then check if cnt is greater than mx. If it is, this is the new maximum frequency, and so mx is updated to cnt, and ans is set to a list containing just root.val.
  • If cnt equals mx, we append root.val to ans because it's a mode with the same frequency as the current maximum.
  • prev is updated to the current node's value: prev = root.val.
  • Recursive calls are made to visit the right subtree: dfs(root.right).

After the dfs function has completed the in-order traversal, the ans list will have the mode(s). The Solution class's findMode function then returns ans. The result is that all modes in the BST are found in a single pass through the tree, which is an efficient use of time and space.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

Example Walkthrough

Let's illustrate the solution with a small example. Suppose our BST looks like this:

1   2
2  / \
3 1   2

The BST contains duplicates, and we want to find the mode. In this case, the mode is 2, since it occurs more frequently than any other number.

Now, let's walk through how the solution processes this BST:

  1. We start with an in-order traversal of the BST, visiting the left child first, then the current node, and finally the right child.
  2. Begin the traversal. The dfs function runs:
    • The dfs function visits the leftmost node which is 1.
    • Since this is our first visit, we compare prev and root.val. They are different (prev is None at the start, and root.val is 1), so we set cnt to 1.
    • As this is the first value we've seen, mx is also set to 1, and ans is updated to [1] because cnt equals mx at this point.
    • We update prev to 1 now that we have processed this node.
  3. Up next, we backtrack and visit the root node which has a value 2. Now, prev is 1:
    • prev (1) does not match root.val (2), so we set cnt to 1.
    • Currently, cnt does not exceed mx, so ans remains the same.
    • We update prev to 2.
  4. Finally, we visit the right child which also has a value of 2:
    • This time, prev matches root.val, so we increment cnt to 2.
    • Now cnt (2) is greater than mx (1), so we have a new mode. Therefore, we update mx to 2, and reset ans to [2], the new mode.
  5. The traversal is now complete, and since there are no more nodes to visit, ans contains the mode(s).

In this example, the output is [2], which is the correct mode of the given BST.

This walkthrough demonstrates the effectiveness of the algorithm as it leverages the BST property to perform an in-order traversal and identify the most frequently occurring element with the need for any additional data structures for frequency counting, making it space efficient.

Solution Implementation

1# Definition for a binary tree node.
2class TreeNode:
3    def __init__(self, val=0, left=None, right=None):
4        self.val = val
5        self.left = left
6        self.right = right
7
8class Solution:
9    def findMode(self, root: TreeNode) -> List[int]:
10        # Helper function to perform in-order traversal
11        def in_order_traversal(node):
12            if node is None:
13                return
14            nonlocal max_count, previous_value, modes, current_count
15            # Traverse the left subtree
16            in_order_traversal(node.left)
17
18            # Update the count for the current value
19            # If the current value matches the previous value, increment the count; 
20            # Otherwise, reset the count to 1 for the new value
21            current_count = current_count + 1 if previous_value == node.val else 1
22
23            # If the current count exceeds the max_count found so far,
24            # update max_count and reset modes with the current value
25            if current_count > max_count:
26                modes = [node.val]
27                max_count = current_count
28            # If the current count matches the max_count,
29            # add the current value to the list of modes
30            elif current_count == max_count:
31                modes.append(node.val)
32
33            # Update the previous_value to the current node's value
34            previous_value = node.val
35
36            # Traverse the right subtree
37            in_order_traversal(node.right)
38
39        # Initialize variables
40        previous_value = None  # Stores the previously seen value
41        max_count = current_count = 0  # max_count is the maximum frequency of any value,
42                                       # current_count is the frequency of the current node value
43        modes = []  # Stores the modes
44
45        # Perform the in-order traversal starting from the root
46        in_order_traversal(root)
47
48        # Return the list of modes
49        return modes
50
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5// Definition for a binary tree node.
6class TreeNode {
7    int val;
8    TreeNode left;
9    TreeNode right;
10    TreeNode() {}
11    TreeNode(int val) { this.val = val; }
12    TreeNode(int val, TreeNode left, TreeNode right) {
13        this.val = val;
14        this.left = left;
15        this.right = right;
16    }
17}
18
19class Solution {
20    private int maxFrequency;
21    private int currentCount;
22    private TreeNode previousNode;
23    private List<Integer> modes;
24
25    // Finds the mode(s) in a binary search tree.
26    public int[] findMode(TreeNode root) {
27        modes = new ArrayList<>();
28        inorderTraversal(root);
29        int[] result = new int[modes.size()];
30        for (int i = 0; i < modes.size(); ++i) {
31            result[i] = modes.get(i);
32        }
33        return result;
34    }
35
36    // Helper function to perform inorder traversal of the binary tree.
37    private void inorderTraversal(TreeNode node) {
38        if (node == null) {
39            return;
40        }
41
42        // Traverse the left subtree
43        inorderTraversal(node.left);
44
45        // Update the current count of the current value
46        // If it's the same as the previous node's value, increment the count; otherwise, reset it to 1
47        currentCount = (previousNode != null && previousNode.val == node.val) ? currentCount + 1 : 1;
48
49        // If current count is greater than max frequency, update max frequency and reset modes list
50        if (currentCount > maxFrequency) {
51            maxFrequency = currentCount;
52            modes = new ArrayList<>(Arrays.asList(node.val));
53        }
54        // If current count is equal to max frequency, add the current value to modes list
55        else if (currentCount == maxFrequency) {
56            modes.add(node.val);
57        }
58
59        // Update previousNode to the current node before traversing right subtree
60        previousNode = node;
61
62        // Traverse the right subtree
63        inorderTraversal(node.right);
64    }
65}
66
1/**
2 * Definition for a binary tree node.
3 */
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    TreeNode() : val(0), left(nullptr), right(nullptr) {}
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    TreeNode* previous;
16    int maxFrequency, currentCount;
17    vector<int> modes;
18
19    /**
20     * Finds the mode(s) in a binary search tree (BST), which are the values with the highest frequency of occurrence.
21     * 
22     * @param root The root node of the BST.
23     * @return A vector containing the mode(s) of the BST.
24     */
25    vector<int> findMode(TreeNode* root) {
26        previous = nullptr;
27        maxFrequency = 0;
28        currentCount = 0;
29        modes.clear();
30      
31        inOrderTraversal(root);
32      
33        return modes;
34    }
35  
36    /**
37     * In-order depth-first search (DFS) traversal of the BST to find the mode(s).
38     * 
39     * @param node The current node being visited.
40     */
41    void inOrderTraversal(TreeNode* node) {
42        if (!node) return; // Base case: if the current node is null, do nothing.
43
44        // Traverse the left subtree.
45        inOrderTraversal(node->left);
46
47        // Process the current node.
48        if (previous != nullptr && previous->val == node->val) {
49            // If the value of the current node is the same as the previous node's value, increment the count.
50            currentCount++;
51        } else {
52            // Otherwise, reset the count to 1.
53            currentCount = 1;
54        }
55      
56        if (currentCount > maxFrequency) {
57            // If the current count exceeds the max frequency found so far,
58            // clear the current modes and add the new mode.
59            modes.clear();
60            modes.push_back(node->val);
61            maxFrequency = currentCount;
62        } else if (currentCount == maxFrequency) {
63            // If the current count equals the max frequency, add this node's value to the modes.
64            modes.push_back(node->val);
65        }
66      
67        // Update the previous node to the current one.
68        previous = node;
69
70        // Traverse the right subtree.
71        inOrderTraversal(node->right);
72    }
73};
74
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    val: number;
6    left: TreeNode | null;
7    right: TreeNode | null;
8
9    constructor(val: number, left?: TreeNode, right?: TreeNode) {
10        this.val = val === undefined ? 0 : val;
11        this.left = left === undefined ? null : left;
12        this.right = right === undefined ? null : right;
13    }
14}
15
16let previous: TreeNode | null = null;
17let maxFrequency: number = 0;
18let currentCount: number = 0;
19let modes: number[] = [];
20
21/**
22 * Finds the modes in a binary search tree (BST), which are the values with the highest frequency of occurrence.
23 * @param root The root node of the BST.
24 * @returns An array containing the modes of the BST.
25 */
26function findMode(root: TreeNode | null): number[] {
27    previous = null;
28    maxFrequency = 0;
29    currentCount = 0;
30    modes = [];
31
32    inOrderTraversal(root);
33
34    return modes;
35}
36
37/**
38 * Performs an in-order traversal of the BST to find the modes.
39 * @param node The current node in the traversal.
40 */
41function inOrderTraversal(node: TreeNode | null): void {
42    if (!node) return; // Base case: If the current node is null, return.
43
44    // Traverse the left subtree.
45    inOrderTraversal(node.left);
46
47    // Process the current node.
48    if (previous && node.val === previous.val) {
49        // If the current node value is the same as the previous node's value, increment the count.
50        currentCount++;
51    } else {
52        // Otherwise, reset the count to 1.
53        currentCount = 1;
54    }
55
56    if (currentCount > maxFrequency) {
57        // If the current count is greater than the max frequency found so far,
58        // clear the modes array and add the new mode.
59        modes = [node.val];
60        maxFrequency = currentCount;
61    } else if (currentCount === maxFrequency) {
62        // If the current count is equal to the max frequency, add this node's value to the modes.
63        modes.push(node.val);
64    }
65
66    // Update the previous node to the current node for the next iteration.
67    previous = node;
68
69    // Traverse the right subtree.
70    inOrderTraversal(node.right);
71}
72
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which data structure is used in a depth first search?

Time and Space Complexity

The time complexity of the provided code is O(N), where N is the number of nodes in the binary tree. This is because the in-order traversal performed by the dfs function visits each node exactly once.

The space complexity of the code is O(H), where H is the height of the binary tree, due to the call stack during the recursive traversals. In the worst-case scenario of a skewed tree, the height H can be N, leading to a space complexity of O(N). Additionally, the space required to store the modes in ans does not exceed O(N) (in the case where all elements are the same and hence the mode list contains all elements), but it does not affect the worst-case space complexity which is dominated by the recursive stack.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Depth first search can be used to find whether two components in a graph are connected.

Recommended Readings

Everything About Trees

Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and

DFS Fundamentals

https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS

Binary Search Tree Intro

Binary Search Tree Intro Definition A Binary Search Tree or BST is a rooted binary tree with the value of each internal node being greater than all the values in the respective node's left subtree and less than the ones in its right subtree An empty tree is a BST since it satisfies the

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ