Problem

Given the root of a binary search tree (BST) with duplicates, return all themode(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.

Examples

Example 1

1
2
3
4
5


![](https://assets.leetcode.com/uploads/2021/03/11/mode-tree.jpg)

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

Example 2

1
2

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

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 that without using any extra space? (Assume that the implicit stack space incurred due to recursion does not count).

Solution

Method 1 – Inorder Traversal with Frequency Counting

Intuition

Since the tree is a BST, an inorder traversal visits nodes in sorted order. We can count the frequency of each value as we traverse, and track the mode(s) by keeping the maximum frequency seen so far.

Approach

  1. Perform an inorder traversal of the BST.
  2. Use a variable to track the previous value, a counter for the current value, and a variable for the maximum frequency.
  3. When visiting a node:
    • If the value is the same as the previous, increment the counter.
    • Otherwise, reset the counter to 1.
    • If the counter equals the max frequency, add the value to the answer list.
    • If the counter exceeds the max frequency, reset the answer list and update the max frequency.
  4. Return the answer list at the end.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};
class Solution {
public:
    vector<int> findMode(TreeNode* root) {
        vector<int> ans;
        int maxFreq = 0, curFreq = 0, prev = INT_MIN;
        function<void(TreeNode*)> inorder = [&](TreeNode* node) {
            if (!node) return;
            inorder(node->left);
            if (node->val == prev) curFreq++;
            else curFreq = 1;
            if (curFreq == maxFreq) ans.push_back(node->val);
            else if (curFreq > maxFreq) {
                ans = {node->val};
                maxFreq = curFreq;
            }
            prev = node->val;
            inorder(node->right);
        };
        inorder(root);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

type TreeNode struct {
    Val int
    Left *TreeNode
    Right *TreeNode
}
func findMode(root *TreeNode) []int {
    var ans []int
    var maxFreq, curFreq int
    var prev *int
    var inorder func(*TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil { return }
        inorder(node.Left)
        if prev != nil && node.Val == *prev {
            curFreq++
        } else {
            curFreq = 1
        }
        if curFreq == maxFreq {
            ans = append(ans, node.Val)
        } else if curFreq > maxFreq {
            ans = []int{node.Val}
            maxFreq = curFreq
        }
        v := node.Val
        prev = &v
        inorder(node.Right)
    }
    inorder(root)
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class TreeNode {
    int val;
    TreeNode left, right;
}
class Solution {
    private Integer prev = null;
    private int maxFreq = 0, curFreq = 0;
    private List<Integer> ans = new ArrayList<>();
    public int[] findMode(TreeNode root) {
        inorder(root);
        return ans.stream().mapToInt(i->i).toArray();
    }
    private void inorder(TreeNode node) {
        if (node == null) return;
        inorder(node.left);
        if (prev != null && node.val == prev) curFreq++;
        else curFreq = 1;
        if (curFreq == maxFreq) ans.add(node.val);
        else if (curFreq > maxFreq) {
            ans.clear(); ans.add(node.val); maxFreq = curFreq;
        }
        prev = node.val;
        inorder(node.right);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

data class TreeNode(var `val`: Int, var left: TreeNode? = null, var right: TreeNode? = null)
class Solution {
    private var prev: Int? = null
    private var maxFreq = 0
    private var curFreq = 0
    private val ans = mutableListOf<Int>()
    fun findMode(root: TreeNode?): IntArray {
        inorder(root)
        return ans.toIntArray()
    }
    private fun inorder(node: TreeNode?) {
        if (node == null) return
        inorder(node.left)
        if (prev != null && node.`val` == prev) curFreq++ else curFreq = 1
        if (curFreq == maxFreq) ans.add(node.`val`)
        else if (curFreq > maxFreq) {
            ans.clear(); ans.add(node.`val`); maxFreq = curFreq
        }
        prev = node.`val`
        inorder(node.right)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def findMode(self, root: TreeNode) -> list[int]:
        ans = []
        max_freq = cur_freq = 0
        prev = None
        def inorder(node):
            nonlocal prev, cur_freq, max_freq, ans
            if not node: return
            inorder(node.left)
            if prev is not None and node.val == prev:
                cur_freq += 1
            else:
                cur_freq = 1
            if cur_freq == max_freq:
                ans.append(node.val)
            elif cur_freq > max_freq:
                ans = [node.val]
                max_freq = cur_freq
            prev = node.val
            inorder(node.right)
        inorder(root)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

use std::rc::Rc;
use std::cell::RefCell;
impl Solution {
    pub fn find_mode(root: Option<Rc<RefCell<TreeNode>>>) -> Vec<i32> {
        fn inorder(node: Option<Rc<RefCell<TreeNode>>>, prev: &mut Option<i32>, cur_freq: &mut i32, max_freq: &mut i32, ans: &mut Vec<i32>) {
            if let Some(n) = node {
                let n = n.borrow();
                inorder(n.left.clone(), prev, cur_freq, max_freq, ans);
                if let Some(p) = prev {
                    if n.val == *p { *cur_freq += 1; } else { *cur_freq = 1; }
                } else { *cur_freq = 1; }
                if *cur_freq == *max_freq { ans.push(n.val); }
                else if *cur_freq > *max_freq {
                    ans.clear(); ans.push(n.val); *max_freq = *cur_freq;
                }
                *prev = Some(n.val);
                inorder(n.right.clone(), prev, cur_freq, max_freq, ans);
            }
        }
        let mut prev = None;
        let mut cur_freq = 0;
        let mut max_freq = 0;
        let mut ans = vec![];
        inorder(root, &mut prev, &mut cur_freq, &mut max_freq, &mut ans);
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class TreeNode {
    val: number;
    left: TreeNode | null;
    right: TreeNode | null;
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = val ?? 0;
        this.left = left ?? null;
        this.right = right ?? null;
    }
}
class Solution {
    findMode(root: TreeNode | null): number[] {
        let ans: number[] = [];
        let maxFreq = 0, curFreq = 0, prev: number | null = null;
        function inorder(node: TreeNode | null) {
            if (!node) return;
            inorder(node.left);
            if (prev !== null && node.val === prev) curFreq++;
            else curFreq = 1;
            if (curFreq === maxFreq) ans.push(node.val);
            else if (curFreq > maxFreq) {
                ans = [node.val];
                maxFreq = curFreq;
            }
            prev = node.val;
            inorder(node.right);
        }
        inorder(root);
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the tree. Each node is visited once.
  • 🧺 Space complexity: O(h), where h is the height of the tree due to recursion stack.