Vultr DocsLatest Content

Find Mode in Binary Search Tree

Updated on 27 May, 2025
Find Mode in Binary Search Tree header image

Problem Statement

In this task, we are given the root of a binary search tree (BST), where the tree might contain duplicate values. The goal is to identify all modes in the tree. A mode is defined as the value or values that occur most frequently within the BST. If multiple values tie for highest frequency, all such values need to be returned, and the order in which these modes are returned does not matter.

A binary search tree holds the property where:

  • The left subtree of any node has keys that are less than or equal to the key of the node.
  • The right subtree of any node has keys that are greater than or equal to the key of the node.
  • Both the left and right subtrees of any node are also valid binary search trees.

This problem requires designing an approach that can efficiently traverse the tree and detect the modes.

Examples

Example 1

Input:

root = [1,null,2,2]

Output:

[2]

Example 2

Input:

root = [0]

Output:

[0]

Constraints

  • The number of nodes in the tree is in the range [1, 104].
  • -105 <= Node.val <= 105

Approach and Intuition

The challenge involves determining the most frequently occurring elements in a BST, which involves tracking the frequencies of elements and identifying the highest frequency. Let’s break down a feasible approach:

  1. Traverse the tree:

    • We can use any tree traversal method (in-order, pre-order, post-order) but using in-order traversal is particularly advantageous for BSTs since it yields values in a sorted order. This makes it easier to count consecutive duplicates.

  2. Count frequencies of each element:

    • Maintain a current count for consecutive nodes with the same value. Since the in-order traversal of a BST yields elements in non-decreasing order, this step can be efficiently carried out.

  3. Determine the highest frequency:

    • While traversing, keep track of the maximum frequency observed. This requires comparing the count of the current value with a previously stored maximum frequency.

  4. Collect the modes:

    • If a node’s frequency matches the highest frequency, it should be added to the result list of modes.
    • If a node’s frequency surpasses the previously known highest frequency, update the highest frequency and reset the result list with this new node value.

  5. Handle edge cases:

    • For trees with a single node, the mode will trivially be the value of this node.

These steps need to be implemented taking care of efficiency, especially given the constraints on the number of nodes and their possible values. A well-constructed traversal and counting mechanism can perform this task within linear time relative to the number of nodes.

Solutions

  • C++
  • Java
  • Python
cpp 
class Solution {
public:
    vector<int> getMode(TreeNode* root) {
        vector<int> modeValues;
        int highestFrequency = 0;
        int currentFrequency = 0;
        int value;

        TreeNode* current = root;
        while (current != nullptr) {
            if (current->left != nullptr) {
                TreeNode* pre = current->left;
                while (pre->right != nullptr && pre->right != current) {
                    pre = pre->right;
                }

                if (pre->right == nullptr) {
                    pre->right = current;
                    current = current->left;
                } else {
                    pre->right = nullptr;
                    if (current->val == value) {
                        currentFrequency++;
                    } else {
                        currentFrequency = 1;
                        value = current->val;
                    }

                    if (currentFrequency > highestFrequency) {
                        modeValues.clear();
                        highestFrequency = currentFrequency;
                    }
                    if (currentFrequency == highestFrequency) {
                        modeValues.push_back(current->val);
                    }
                    current = current->right;
                }
            } else {
                if (current->val == value) {
                    currentFrequency++;
                } else {
                    currentFrequency = 1;
                    value = current->val;
                }

                if (currentFrequency > highestFrequency) {
                    modeValues.clear();
                    highestFrequency = currentFrequency;
                }
                if (currentFrequency == highestFrequency) {
                    modeValues.push_back(current->val);
                }
                current = current->right;
            }
        }
        return modeValues;
    }
};

The provided C++ solution aims to find the mode (the most frequently occurring value) in a Binary Search Tree (BST). It is implemented within a class method named getMode, which takes the root of the tree as input and returns a vector of integers representing the mode values.

  • The method getMode initializes several variables: modeValues to store the mode(s), highestFrequency to track the number of times the most frequent element has appeared, currentFrequency to count the occurrences of the current value, and value to remember the last accessed value in the tree.
  • A pointer current is used to traverse the tree. The method uses Morris Traversal, a threaded binary tree approach that does not require additional data structures for tree traversal.

The algorithm follows these key steps to determine the mode:

  1. Traverse the BST using the current pointer, starting with the root.
  2. For each node:
    • Check if it has a left child. If so, find the rightmost node of the left subtree (inorder predecessor).
    • Utilize the inorder predecessor to create a temporary thread back to the current node, facilitating an efficient in-order traversal without recursion or a stack.
    • If moving back to a node from its left subtree (detected by the temporary thread), increase or reset currentFrequency based on the value comparison to value.
    • Update highestFrequency and potentially clear and update modeValues based on the new frequency comparison.
    • Proceed to the right subtree if there is no left child or after revisiting a node with a left child.
  3. Return modeValues which contains the most frequent element(s).

This method efficiently finds the modes without using additional space for recursion or node stack, providing an in-place solution with a time complexity closely tied to the number of nodes (O(n)) and minimizing additional space usage.

java 
class Solution {
    public int[] findMode(TreeNode root) {
        int maximumCounter = 0;
        int currentCounter = 0;
        int currentNumber = 0;
        List<Integer> modes = new ArrayList();
        
        TreeNode iterator = root;
        while (iterator != null) {
            if (iterator.left != null) {
                // Locating predecessor
                TreeNode predecessor = iterator.left;
                while (predecessor.right != null && predecessor.right != iterator) {
                    predecessor = predecessor.right;
                }
                
                if (predecessor.right == null) {
                    predecessor.right = iterator;
                    iterator = iterator.left;
                } else {
                    predecessor.right = null;

                    // Count the current value
                    if (iterator.val == currentNumber) {
                        currentCounter++;
                    } else {
                        currentNumber = iterator.val;
                        currentCounter = 1;
                    }

                    if (currentCounter > maximumCounter) {
                        modes.clear();
                        maximumCounter = currentCounter;
                    }
                    if (currentCounter == maximumCounter) {
                        modes.add(iterator.val);
                    }

                    iterator = iterator.right;
                }
            } else {
                if (iterator.val == currentNumber) {
                    currentCounter++;
                } else {
                    currentNumber = iterator.val;
                    currentCounter = 1;
                }

                if (currentCounter > maximumCounter) {
                    modes.clear();
                    maximumCounter = currentCounter;
                }
                if (currentCounter == maximumCounter) {
                    modes.add(iterator.val);
                }

                iterator = iterator.right;
            }
        }
        
        int[] resultArray = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            resultArray[i] = modes.get(i);
        }
        
        return resultArray;
    }
}

The given Java program defines a method to determine the mode(s) of a Binary Search Tree (BST). The mode is the value that appears most frequently in the tree.

  • Initialize three variables: maximumCounter to hold the maximum frequency of any element, currentCounter to count the occurrences of the current element, and currentNumber to hold the value of the element currently being counted.
  • Utilize a List<Integer> called modes to store elements that occur with the maximum frequency.
  • Use Morris Traversal to traverse the BST without additional space. During traversal:
    • If the current node's left child is not null, find the predecessor. If the predecessor's right pointer is null, make it point to the current node (iterator) and move the iterator to its left child. If the predecessor's right pointer points to the iterator, reset it, and process the current node.
    • If the left child is null, process the current node immediately.
  • Update currentCounter and currentNumber based on the value of the node currently being iterated upon. If currentCounter exceeds maximumCounter, clear modes and update maximumCounter. If currentCounter equals maximumCounter, add the current value to modes.
  • After completing the tree traversal, convert the modes list to an array and return it.

This approach ensures an in-place computation of the modes without using additional data structures like hash maps, leveraging Morris Traversal for efficient space utilization.

python 
class Solution:
    def findFrequentElements(self, root: Optional[TreeNode]) -> List[int]:
        highest_count = 0
        current_count = 0
        current_value = 0
        result = []
        
        node = root
        while node:
            if node.left:
                # Traverse to the leftmost right child
                predecessor = node.left
                while predecessor.right:
                    predecessor = predecessor.right
                
                predecessor.right = node
                
                # Removing left link to avoid cycle
                temp = node.left
                node.left = None
                node = temp
            else:
                # Process the current node
                value = node.val
                if value == current_value:
                    current_count += 1
                else:
                    current_count = 1
                    current_value = value

                if current_count > highest_count:
                    result = []
                    highest_count = current_count

                if current_count == highest_count:
                    result.append(value)
                
                node = node.right
        
        return result

The solution provided is designed to find the mode (most frequently occurring element) in a Binary Search Tree (BST) using Python. The approach utilized in this solution is Morris Traversal, which is a space-efficient tree traversal technique that does not use recursion or additional memory for call stacks.

The solution performs an in-order traversal of the BST, which inherently visits elements in non-decreasing order due to the properties of the BST. During this traversal, it processes each node as follows:

  • Traverse to the leftmost child of the subtree and using right pointers to keep track of visited nodes, thus avoiding the need for additional data structures for backtracking.
  • Compare each node's value with the current value being evaluated.
    • If it matches, increment a counter for occurrences of this value.
    • If it doesn't match or if it's the first node, reset the counter and set the current node's value as the new value to be counted.
  • Determine if the value being counted is more frequent than the previously recorded highest frequency.
    • If so, reset the results list with this more frequent value.
    • If the frequency matches the highest frequency, add the current value to the results list.

Upon completion of the traversal, the solution returns the result list, which contains the mode(s) of the tree. This method offers an efficient way to determine the mode without additional space complexity, making it particularly suitable for large trees where auxiliary space is a concern.

Comments

No comments yet.