## Most Common Item In A Binary Search Tree

### July 18, 2017

Today’s exercise is an interview question:

You are given a binary search tree in which all keys in the left child of a node are less than or equal to the key of the current node and all keys in the right child of a node are greater than or equal to the key of the current node. Find the most common key in the binary search tree. You may use O(

n) time and O(1) space.

Your task is to write a program to find the most common node in a binary search tree, subject to the given constraints. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Advertisements

Assuming that the keys are ordered in such a way that equal keys will all be consecutive in an inorder traversal (as they would be for integers), doesn’t that suggest “inorder traversal -> find longest run of consecutive identical items”?

I think that would be something like pseudo-Haskell “maximumBy length . group . inorder” (tweaked to use O(1) space if necessary).

It seems to me that O(n) is possible. Walk the tree (O(n)) and count the occurences of all values (using a hash table).

We can certainly compute the desired result in O(n) time with a simple in-order traversal (or treefoldl), and a fixed set of variables (current,best) x (value,count). Where that falls down is in requiring O(depth(tree)) stack space. I suspect that we can get that down to O(1) space if we are allowed to smash the tree (flattening it to a list on the fly), but I am not sure. There is certainly no need for a hash table.

[…] written about binary search trees on several occasions, most recently here. Binary search trees are a fruitful source of exercises, and we have another one […]

Here’s a solution in Java. Morris traversal is used for in-order traversal (a recursive solution would require more than O(1) space). The sorted order of values from the in-order traversal is relied upon for tracking the mode.

Example output follows the code in my last post.

My implementation with O(n) time and O(1) space in common lisp: