Search⌘ K
AI Features
Home
Courses
Decode the Coding Interview in Swift: Real-World Examples

Feature #9: Products in Price Range

Explore how to implement a product search feature that finds all items within a selected price range using preorder traversal on a binary search tree. Understand recursive approaches to optimize searching by limiting traversal to relevant nodes, and learn about the associated time and space complexities involved in this algorithm.

We'll cover the following...

Description

In this feature of the Amazon website, we want to implement a search filter that searches for products in a given price range. The product data is given to us in the form of a binary search tree, where the values are the prices. We will be given the parameters low and high; these represent the price range the user selected. This range is inclusive.

For example, let’s consider the following list of products that are mapped to their prices. The prices have been rounded off for simplicity.

These products have been stored in the binary search tree based on their prices as such:

%0 node_1 9 node_2 6 node_1->node_2 node_3 14 node_1->node_3 node_1612742913146 1 node_2->node_1612742913146 node_1612742984288 8 node_2->node_1612742984288 node_1612743001880 5 node_1612742913146->node_1612743001880 node_1612742980226 20 node_3->node_1612742980226 node_1612742984371 17 node_1612742980226->node_1612742984371 node_1612742965159 30 node_1612742980226->node_1612742965159
Binary Tree of Product Prices

Now, let’s assume that the price range selected by the user is low = 7 and high = 20. In this case, our function should return [9, 8, 14, 20, 17]. The order of products in the output does not matter.

Solution

We can implement this ...