Most frequent element in a Binary Search Tree

algorithm

Solution

This problem is equivalent to finding the most frequent element in a sorted array - the same algorithm applies:

- Start the counter at zero

- Increment the counter while the current element is equal to the prior one

- When you find a different element, compare the counter to the current best run; replace if necessary

- Continue to the next element

The only difference is that instead of an array traversal with a loop you do a tree traversal with a recursive function. In both cases the algorithm is linear in time in the number of elements in the tree. If the tree is balanced, the algorithm requires `O(LogN)` space on the invocation stack.

Problem

Original source