Finding the mode in Binary Search Tree

Question

I saw this question has been around on this site, but I would like to discuss one issue please about tracking prev value in the code below. Given the following solution for finding the Mode in binary search tree,

class Solution {
    Integer prev = null;
    int count = 1;
    int max = 0;
    public int[] findMode(TreeNode root) {
         //this is expandable, but int [] array is not expandable
        List<Integer> modes = new ArrayList();
        traverse(root, modes);
        int[] result = new int[modes.size()];
        for (int i=0; i<modes.size(); i++){
            result[i] = modes.get(i);
        }
        
        return result;

    }
    //In BST, do inorder since that way nodes will be sorted L < root < R
    public void traverse(TreeNode root, List<Integer> modes){
        if(root == null) return; //dont do anything

        traverse(root.left,  modes);
        
        if(prev != null){
            if(prev == root.val){
                count ++;
            } else{
                count =1;
            }
        }
        
        if(count > max){
            max = count; 
            modes.clear(); //delete all previous modes as we find a new one
            modes.add(root.val);
        } else if(count == max) { // we find another mode that has same # of occurrences
            modes.add(root.val);
        }
        
        prev = root.val; 
        
        traverse( root.right,  modes);
    }
}

Now, the prev variable is supposed to capture the previous node value so that when we enter to node's left child as the code show, we will immediately compare it to left child of that node. For example, if prev = 5, then once we go up to 10, the new prev is prev = root.val;, then we got to 15 the right child of 10. But we don't compare prev to 15, but to 10 as we immediately go left in the code once, so we compare prev = 10 to node.val in if(prev == root.val) line. We go from there for all other nodes.

Problem: Suppose the node that is immediately left to 30 is 25 and not 20, then the trick used in this solution won't work in this case, what do you think pleas?

Answer 1

The algorithm is performing an in-order tree traversal, which does this:

1. traverse the left subtree by recursively calling the in-order function.
2. access the data part of the current node.
3. traverse the right subtree by recursively calling the in-order function.

In a binary search tree, because of the order of the nodes, an in-order traversal is visiting the nodes in ascending sorted order.

I think this picture (courtesy Wikipedia) will help to explain what's happening:

In-order traversal will visit the nodes in this order:

A, B, C, D, E, F, G, H, I;

Now since we are visiting the nodes is ascending sorted order, duplicates will be grouped together. Therefore, we just need to compare the current node with the previous node to find duplicates.

In your first example tree, the nodes are visited in this order: 5, 10, 10, 12, 15, 15, 16, 18, 20, 20, 20, 20, 25, 28, 30, 32. The mode is 20.

In your second example tree, the nodes are visited in this order: 5, 10, 10, 12, 15, 15, 16, 18, 20, 20, 20, 25, 30, 32. The mode is 20.