Pular para o conteúdo principal

Find Mode in Binary Search Tree

Given a binary search tree, return its mode (you may assume the answer is unique). If the tree is empty, return -1.

Note: The mode is the most frequently occurring value in the tree.

Example(s)​

Example 1:

Input:
        2
       / \
      1   2

Output: 2
Explanation:
Value 1 appears 1 time
Value 2 appears 2 times (mode)
Mode: 2

Example 2:

Input:
         7
        / \
      4     9
     / \   / \
    1   4 8   9
               \
                9

Output: 9
Explanation:
Value 1 appears 1 time
Value 4 appears 2 times
Value 7 appears 1 time
Value 8 appears 1 time
Value 9 appears 3 times (mode)
Mode: 9

Example 3:

Input:
    5
   / \
  3   7

Output: 5
Explanation:
All values appear once, so any value can be mode.
Since answer is unique, return root value: 5

Example 4:

Input: (empty tree)

Output: -1
Explanation:
Empty tree, return -1.

Solution​

The solution uses Hash Map with DFS:

  1. Traverse tree: Use DFS to visit all nodes
  2. Count frequencies: Use hash map to count occurrences of each value
  3. Find maximum: Find value with maximum frequency
  4. Return mode: Return the most frequent value

JavaScript Solution - Hash Map

/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/

/**
* Find mode in BST
* @param {TreeNode} root - Root of binary search tree
* @return {number} - Mode (most frequent value)
*/
function findMode(root) {
if (!root) return -1;

const freq = new Map();
let maxFreq = 0;
let mode = -1;

/**
 * DFS to count frequencies
 */
function dfs(node) {
  if (!node) return;
  
  // Count current node value
  const count = (freq.get(node.val) || 0) + 1;
  freq.set(node.val, count);
  
  // Update mode if current value has higher frequency
  if (count > maxFreq) {
    maxFreq = count;
    mode = node.val;
  }
  
  // Recursively process children
  dfs(node.left);
  dfs(node.right);
}

dfs(root);
return mode;
}

// Helper function to create tree nodes for testing
function TreeNode(val, left, right) {
this.val = val;
this.left = left;
this.right = right;
}

// Test cases
// Example 1: [2, 1, 2]
const tree1 = new TreeNode(2,
new TreeNode(1),
new TreeNode(2)
);
console.log('Example 1:', findMode(tree1)); // 2

// Example 2: [7, 4, 9, 1, 4, 8, 9, null, null, null, null, null, 9]
const tree2 = new TreeNode(7,
new TreeNode(4, new TreeNode(1), new TreeNode(4)),
new TreeNode(9, new TreeNode(8), new TreeNode(9, null, new TreeNode(9)))
);
console.log('Example 2:', findMode(tree2)); // 9
Output:
Click "Run Code" to execute the code and see the results.

Alternative Solution (In-Order Traversal)​

Here's an alternative using in-order traversal (takes advantage of BST property):

/**
 * Alternative: In-order traversal (BST gives sorted order)
 * Can count consecutive values more efficiently
 */
function findModeInOrder(root) {
  if (!root) return -1;
  
  let maxFreq = 0;
  let mode = -1;
  let currentVal = null;
  let currentCount = 0;
  
  function inOrder(node) {
    if (!node) return;
    
    inOrder(node.left);
    
    // Count consecutive values (since in-order gives sorted order)
    if (node.val === currentVal) {
      currentCount++;
    } else {
      currentVal = node.val;
      currentCount = 1;
    }
    
    // Update mode
    if (currentCount > maxFreq) {
      maxFreq = currentCount;
      mode = node.val;
    }
    
    inOrder(node.right);
  }
  
  inOrder(root);
  return mode;
}

Complexity​

  • Time Complexity: O(n) - Where n is the number of nodes in the tree. We visit each node once.
  • Space Complexity:
    • Hash Map: O(n) - For the frequency map (worst case: all values unique)
    • In-Order: O(h) - For the recursion stack, where h is the height of the tree

Approach​

The solution uses Hash Map with DFS:

  1. Traverse tree:

    • Use DFS (any order) to visit all nodes
    • Can use pre-order, in-order, or post-order

  2. Count frequencies:

    • Use hash map to count occurrences of each value
    • freq[value] = count

  3. Track maximum:

    • Keep track of maximum frequency seen so far
    • Update mode when we find a value with higher frequency

  4. Return mode:

    • After traversal, return the value with maximum frequency

Key Insights​

  • Hash map: Efficiently count frequencies of all values
  • Any traversal: DFS order doesn't matter for counting
  • BST property: In-order gives sorted values (can optimize)
  • O(n) time: Must visit all nodes
  • O(n) space: Hash map in worst case

Step-by-Step Example​

Let's trace through Example 1:

Tree:
        2
       / \
      1   2

freq = {}
maxFreq = 0
mode = -1

DFS traversal:
  dfs(2):
    freq[2] = 1
    maxFreq = 1, mode = 2
    
    dfs(1):
      freq[1] = 1
      maxFreq = 1, mode = 2 (no change)
    
    dfs(2):
      freq[2] = 2
      maxFreq = 2, mode = 2 ✓

Result: mode = 2

Let's trace through Example 2:

Tree:
         7
        / \
      4     9
     / \   / \
    1   4 8   9
               \
                9

freq = {}
maxFreq = 0
mode = -1

DFS traversal:
  Process nodes in any order, count frequencies:
    freq[1] = 1
    freq[4] = 2
    freq[7] = 1
    freq[8] = 1
    freq[9] = 3
    
  Track maximum:
    maxFreq = 3
    mode = 9 ✓

Result: mode = 9

Visual Representation​

Example 1:
        2
       / \
      1   2

Frequencies:
  Value 1: count = 1
  Value 2: count = 2 (mode) ✓

Example 2:
         7
        / \
      4     9
     / \   / \
    1   4 8   9
               \
                9

Frequencies:
  Value 1: count = 1
  Value 4: count = 2
  Value 7: count = 1
  Value 8: count = 1
  Value 9: count = 3 (mode) ✓

Edge Cases​

  • Empty tree: Return -1
  • Single node: Return that node's value
  • All unique values: Return any value (problem says answer is unique)
  • All same value: Return that value
  • Tie in frequencies: Problem says answer is unique, so this shouldn't happen

Important Notes​

  • Mode definition: Most frequently occurring value
  • Unique answer: Problem guarantees unique mode
  • BST property: Can use in-order for optimization, but hash map works for any tree
  • O(n) time: Must visit all nodes
  • O(n) space: Hash map in worst case

Why Hash Map Works​

Key insight:

  • We need to count frequency of each value
  • Hash map provides O(1) insertion and lookup
  • After counting all values, find the maximum frequency
  • This is the most straightforward approach

BST advantage:

  • In-order traversal gives sorted values
  • Can count consecutive values without hash map
  • But hash map approach is simpler and works for any tree
  • Find Mode in Array: Similar problem for arrays
  • Most Frequent Subtree Sum: Different tree problem
  • Kth Most Frequent Element: Different frequency problem
  • Top K Frequent Elements: Different problem

Takeaways​

  • Hash map efficiently counts frequencies
  • Any DFS traversal works for counting
  • O(n) time to visit all nodes
  • O(n) space for hash map
  • Simple approach that works for any tree