Find Mode in Binary Search Tree

Easy
1871.

Find Mode in Binary Search Tree

Find Mode in Binary Search Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

You are given the root of a binary search tree that may contain duplicate values. Return all of its modes — the values that occur most often — in ascending order.

Here a BST satisfies, at every node: every value in the left subtree is <= the node's value, and every value in the right subtree is >= it.

Example 1

Input
root = [1,null,2,2]
Output
[2]
Explanation
2 occurs twice and 1 once.

Example 2

Input
root = [0]
Output
[0]

Example 3

Input
root = [5,3,7,3,5,6,7]
Output
[3,5,7]
Explanation
3, 5 and 7 each occur twice; 6 once. All three are modes, listed ascending.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4]
  • -10^5 <= Node.val <= 10^5

Follow-up: Could you do it without a hash map — using no extra space apart from the recursion or traversal stack?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var findMode = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find Mode in Binary Search Tree — Problem & Solution

Find Mode in Binary Search Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Find Mode in Binary Search Tree is an easy coding problem on depth-first search and trees, asked in Amazon, Google and Microsoft interviews.

Problem statement

You are given the root of a binary search tree that may contain duplicate values. Return all of its modes — the values that occur most often — in ascending order.

Here a BST satisfies, at every node: every value in the left subtree is <= the node's value, and every value in the right subtree is >= it.

Example 1

Input: root = [1,null,2,2]
Output: [2]
Explanation: 2 occurs twice and 1 once.

Example 2

Input: root = [0]
Output: [0]

Example 3

Input: root = [5,3,7,3,5,6,7]
Output: [3,5,7]
Explanation: 3, 5 and 7 each occur twice; 6 once. All three are modes, listed ascending.

Constraints

  • The number of nodes in the tree is in the range [1, 10^4]
  • -10^5 <= Node.val <= 10^5

Follow-up: Could you do it without a hash map — using no extra space apart from the recursion or traversal stack?

Hints for Find Mode in Binary Search Tree

  1. Hint 1

    An inorder walk of a BST visits its values in non-decreasing order, so equal values come out next to each other.

  2. Hint 2

    Count the length of each run of equal values as the walk produces them, remembering the longest run so far.

  3. Hint 3

    When a run beats the best count, restart the answer with that value; when it ties, append it. Values arrive ascending, so the answer is already sorted.

How to solve Find Mode in Binary Search Tree

Inorder traversal turns the BST into a sorted sequence, where every value's copies form one contiguous run. The modes are the values with the longest runs, found in one pass with a run counter and a best counter — no hash map.

Approach

  1. Walk the tree inorder (an explicit stack or recursion).
  2. For each value: if it equals the previous one, increment count; otherwise reset count = 1.
  3. If count > best, set best = count and make the answer just [value]; if count == best, append value.
  4. After the walk, the answer holds every mode in ascending order.

Why it works

With left <= node <= right at every node, inorder emits the values in non-decreasing order, so all copies of a value are consecutive and count reaches that value's total frequency at its last copy. A value is kept in the answer exactly when that frequency equals the final maximum — any value kept earlier for a smaller best is discarded when the answer restarts.

Complexity

  • Time — O(n)
  • Space — O(h) for the traversal stack, besides the output

Pitfalls

  • Restart the list when count > best and append only when count == best; a value appended on a tie and then extended simply restarts the list with itself, so it is never listed twice.
  • Several modes are possible; all of them must be returned.
  • Do not assume distinct values: this BST allows duplicates on either side.

Reference solution

Python

from typing import List, Optional

def findMode(root: Optional[TreeNode]) -> List[int]:
    modes = []
    best = count = 0
    prev = None
    stack = []
    cur = root
    while cur is not None or stack:
        while cur is not None:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        count = count + 1 if cur.val == prev else 1
        prev = cur.val
        if count > best:
            best = count
            modes = [cur.val]
        elif count == best:
            modes.append(cur.val)
        cur = cur.right
    return modes

Java

public static int[] findMode(TreeNode root) {
    List<Integer> modes = new ArrayList<>();
    int best = 0, count = 0;
    long prev = Long.MIN_VALUE;
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode cur = root;
    while (cur != null || !stack.isEmpty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        count = cur.val == prev ? count + 1 : 1;
        prev = cur.val;
        if (count > best) {
            best = count;
            modes.clear();
            modes.add(cur.val);
        } else if (count == best) {
            modes.add(cur.val);
        }
        cur = cur.right;
    }
    int[] res = new int[modes.size()];
    for (int i = 0; i < res.length; i++) res[i] = modes.get(i);
    return res;
}

C++

vector<int> findMode(TreeNode* root) {
    vector<int> modes;
    int best = 0, count = 0;
    long long prev = LLONG_MIN;
    vector<TreeNode*> stack;
    TreeNode* cur = root;
    while (cur || !stack.empty()) {
        while (cur) {
            stack.push_back(cur);
            cur = cur->left;
        }
        cur = stack.back();
        stack.pop_back();
        count = cur->val == prev ? count + 1 : 1;
        prev = cur->val;
        if (count > best) {
            best = count;
            modes.assign(1, cur->val);
        } else if (count == best) {
            modes.push_back(cur->val);
        }
        cur = cur->right;
    }
    return modes;
}

JavaScript

var findMode = function(root) {
    var modes = [], best = 0, count = 0, prev = null;
    var stack = [], cur = root;
    while (cur !== null || stack.length > 0) {
        while (cur !== null) {
            stack.push(cur);
            cur = cur.left;
        }
        cur = stack.pop();
        count = cur.val === prev ? count + 1 : 1;
        prev = cur.val;
        if (count > best) {
            best = count;
            modes = [cur.val];
        } else if (count === best) {
            modes.push(cur.val);
        }
        cur = cur.right;
    }
    return modes;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals