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:

Tree:
        2
       / \
      1   2
Output: 2

Example 2:

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

Solution

JavaScript Solution

JavaScript BST Mode Solution

/**
* 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 the mode in a BST
* @param {TreeNode} root - Root of the BST
* @return {number} - Mode of the BST or -1 if empty
*/
function findMode(root) {
if (!root) return -1;

let currVal = null;
let currCount = 0;
let maxCount = 0;
let mode = null;

function inorder(node) {
  if (!node) return;
  
  inorder(node.left);
  
  if (node.val === currVal) {
    currCount++;
  } else {
    currVal = node.val;
    currCount = 1;
  }
  
  if (currCount > maxCount) {
    maxCount = currCount;
    mode = node.val;
  }
  
  inorder(node.right);
}

inorder(root);
return mode;
}

// Test case 1: [2,1,2]
const tree1 = new TreeNode(2);
tree1.left = new TreeNode(1);
tree1.right = new TreeNode(2);

// Test case 2: [7,4,9,1,4,8,9,null,null,9]
const tree2 = new TreeNode(7);
tree2.left = new TreeNode(4);
tree2.right = new TreeNode(9);
tree2.left.left = new TreeNode(1);
tree2.left.right = new TreeNode(4);
tree2.right.left = new TreeNode(8);
tree2.right.right = new TreeNode(9);
tree2.right.right.right = new TreeNode(9);

// Test cases
console.log(findMode(tree1)); // 2
console.log(findMode(tree2)); // 9
console.log(findMode(null)); // -1

Output:

Click "Run Code" to execute the code and see the results.

Python Solution

Python BST Mode Solution

from typing import Optional

# Definition for a binary tree node.
class TreeNode:
  def __init__(self, val=0, left=None, right=None):
      self.val = val
      self.left = left
      self.right = right

def find_mode(root: Optional[TreeNode]) -> int:
  """
  Find the mode in a BST
  
  Args:
      root: Root of the BST
      
  Returns:
      int: Mode of the BST or -1 if empty
  """
  if not root:
      return -1
  
  curr_val = [None]
  curr_count = [0]
  max_count = [0]
  mode = [None]
  
  def inorder(node):
      if not node:
          return
      
      inorder(node.left)
      
      if node.val == curr_val[0]:
          curr_count[0] += 1
      else:
          curr_val[0] = node.val
          curr_count[0] = 1
      
      if curr_count[0] > max_count[0]:
          max_count[0] = curr_count[0]
          mode[0] = node.val
      
      inorder(node.right)
  
  inorder(root)
  return mode[0]

# Test case 1: [2,1,2]
tree1 = TreeNode(2)
tree1.left = TreeNode(1)
tree1.right = TreeNode(2)

# Test case 2: [7,4,9,1,4,8,9,null,null,9]
tree2 = TreeNode(7)
tree2.left = TreeNode(4)
tree2.right = TreeNode(9)
tree2.left.left = TreeNode(1)
tree2.left.right = TreeNode(4)
tree2.right.left = TreeNode(8)
tree2.right.right = TreeNode(9)
tree2.right.right.right = TreeNode(9)

# Test cases
print(find_mode(tree1))  # 2
print(find_mode(tree2))  # 9
print(find_mode(None))  # -1

Loading Python runtime...

Output:

Click "Run Code" to execute the code and see the results.

Complexity

• Time Complexity: O(n) - Where n is the number of nodes in the tree
• Space Complexity: O(h) - Where h is the height of the tree (recursion stack)

Approach

The solution uses an in-order traversal approach:

1. In-order traversal processes nodes in ascending order (left → root → right)
2. Track current value and count as we traverse
3. Update mode whenever we find a value with higher frequency
4. Return the mode or -1 if the tree is empty

Key Insights

• In-order traversal leverages BST property to process nodes in ascending order
• Single pass through the tree is sufficient to find the mode
• Space optimization using variables instead of storing all frequencies
• Edge case handling for empty trees
• Efficient O(n) time complexity as each node is visited once