O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Binary Search Trees

A Binary Search Tree (BST) is a binary tree with the following additional property. The value at the root node is greater (or equal) than all the values in the left subtree. Likewise, the value is lesser than (or equal) all the values in the right subtree.

We keep things simple and don't consider the multiple equal values case. Rather, we implement dictionaries using binary trees.

A dictionary is a list of (key, value) pairs. A key can occur only once, that is, the key is unique. For example, we could use dictionaries to compute the count of words in a given text input.

The word count algorithm is simple:

words[] = split a string on space characters. for each word, search the dictionary if it is already present. if not in dictionary, ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required