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

Pages: 1 2

3 Responses to “Most Common Item In A Binary Search Tree”

  1. Colin said

    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).

  2. Paul said

    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).

  3. 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: