LeetCode Entry

501. Find Mode in Binary Search Tree

01.11.2023 easy 2023 kotlin

Most frequent elements in a Binary Search Tree

501. Find Mode in Binary Search Tree easy blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/389

Problem TLDR

Most frequent elements in a Binary Search Tree

Intuition

A simple solution is to use a frequency map. Another way is the linear scan of the increasing sequence. For example, 1 1 1 2 2 2 3 3 4 4 4: we can use one counter and drop the previous result if counter is more than the previous max.

Approach

To convert the Binary Search Tree into an increasing sequence, we can do an in-order traversal.

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\), result can be n if numbers are unique

Code

    fun findMode(root: TreeNode?): IntArray {
      val res = mutableListOf<Int>()
      var maxCount = 0
      var count = 0
      var prev = Int.MAX_VALUE
      fun dfs(n: TreeNode) {
        n.left?.let { dfs(it) }
        if (prev == n.`val`) {
          count++
        } else {
          count = 1
          prev = n.`val`
        }
        if (count == maxCount) {
          res += n.`val`
        } else if (count > maxCount) {
          maxCount = count
          res.clear()
          res += n.`val`
        }
        n.right?.let { dfs(it) }
      }
      root?.let { dfs(it) }
      return res.toIntArray()
    }