Find Mode in Binary Search Tree - Practice Coding Problems

Find Mode in Binary Search Tree - Problem

Given the root of a binary search tree (BST) with duplicates, return all the mode(s) (i.e., the most frequently occurred element) in it.

If the tree has more than one mode, return them in any order.

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.

Input & Output

Example 1 — Basic BST

$ Input: root = [1,null,2,2]

› Output: [2]

💡 Note: The value 2 appears twice while 1 appears once. So 2 is the mode.

Example 2 — Multiple Modes

$ Input: root = [0]

› Output: [0]

💡 Note: Single node tree, so 0 is the only and most frequent value.

Example 3 — Balanced BST

$ Input: root = [1,0,2]

› Output: [0,1,2]

💡 Note: All values appear exactly once, so all are modes.

Constraints

The number of nodes in the tree is in the range [1, 10⁴].
-10⁵ ≤ Node.val ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input BST

Binary search tree with duplicate values

Count Frequencies

Count occurrence of each value

Find Modes

Return all values with maximum frequency

Key Takeaway

🎯 Key Insight: BST in-order traversal visits values in sorted order, making duplicate counting very efficient

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is leveraging the BST's in-order traversal property to process values in sorted order. Best approach uses in-order DFS to count consecutive duplicates efficiently. Time: O(n), Space: O(h).

Common Approaches

Approach	Time	Space	Notes
✓ Optimized In-Order DFS	O(n)	O(h)	Use in-order traversal to process values in sorted order, tracking current value frequency
Brute Force - HashMap Count	O(n)	O(n)	Traverse tree and count all values in a hash map, then find maximum frequency

Optimized In-Order DFS — Algorithm Steps

Perform in-order traversal (left-root-right)
Track current value and its consecutive count
Update maximum frequency and modes list as we go
Handle consecutive duplicate values efficiently

Visualization

Tap to expand

Step-by-Step Walkthrough

In-Order Traversal

Visit nodes in sorted order: left → root → right

Count Consecutive

Track current value and consecutive count

Update Modes

Update result when higher frequency found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

int* result;
int resultSize;
int maxCount;
int currentCount;
int prevVal;
int hasPrev;

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void inorder(struct TreeNode* node) {
    if (!node) return;
    
    inorder(node->left);
    
    if (hasPrev && prevVal == node->val) {
        currentCount++;
    } else {
        currentCount = 1;
        prevVal = node->val;
        hasPrev = 1;
    }
    
    if (currentCount > maxCount) {
        maxCount = currentCount;
        resultSize = 1;
        result[0] = node->val;
    } else if (currentCount == maxCount) {
        result[resultSize++] = node->val;
    }
    
    inorder(node->right);
}

int* solution(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if (!root) return NULL;
    
    result = (int*)malloc(1000 * sizeof(int));
    resultSize = 0;
    maxCount = 0;
    currentCount = 0;
    prevVal = -1001;
    hasPrev = 0;
    
    inorder(root);
    
    *returnSize = resultSize;
    return result;
}

int main() {
    printf("[2]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

In-order traversal visits each node exactly once

✓ Linear Growth

Space Complexity

O(h)

Recursion stack depth equals tree height h, plus result array

✓ Linear Space

64.8K Views

Medium Frequency

~15 min Avg. Time

2.4K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized In-Order DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler