# Dictionary Using Balanced BST Lookup Time Complexity

I was going through an article in geeksforgeeks on how to implement dictionary using balanced BST and found this line:

If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree.

I didn't understand how this would be O(M*logn), given balanced BSTs always maintain a max height of O(logn), shouldn't this be (logn)?

## Answer

This quote is taken from a context of searching words in a dictionary:

Trie is an efficient data structure for searching words in dictionaries, search complexity with Trie is linear in terms of word (or key) length to be searched. If we store keys in binary search tree, a well balanced BST will need time proportional to M * log N, where M is maximum string length and N is number of keys in tree. Using trie, we can search the key in O(M) time. So it is much faster than BST.

In a BST these words would be stored such that one node gets one word.

Although in a balanced BST of 𝑁 nodes you need to visit O(log𝑁) nodes to find the targeted value in the worst case, it will also take time to compare a node's string with the target string. As the maximum length of a word is given as 𝑀, the worst case time complexity for each individual string comparison is O(𝑀). As such a comparison happens at each visited node, this gives a total complexity of O(𝑀log𝑁).

## Related Questions

- → What are the pluses/minuses of different ways to configure GPIOs on the Beaglebone Black?
- → JavaScript implementation of printing left view of binary tree is returning incorrect result
- → Reducing an entire subtree with redux combineReducers
- → Binding forms at multiple different mount points with redux-form
- → Delay Paypal payment - Braintree APIs
- → How do I get the postal code from google map's autocomplete api
- → Rails shopify/stripe/braintree/twilio webhooks testing on localhost
- → Issues with preserveAspectRatio, viewBox and layout.size()
- → Rendering a dynamically created family graph with no overlapping using a depth first search?
- → Phaser Collision not working as expected in Arcade
- → Does React always check the whole tree?
- → How to use a recursive filter all single JSON data?
- → Check if Element Present in a JS Object