Search⌘ K
Home
Courses
Decode the Coding Interview in Go: Real-World Examples

Feature #9: Products in Price Range

Explore how to implement a product search filter feature that finds all products within a given price range stored in a binary search tree. Understand how to apply preorder traversal recursively, optimize the search by limiting traversal, and analyze the time and space complexity of your solution. This lesson helps you solve real-world coding interview problems using binary trees in Go.

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. You 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, your function should return [9, 8, 14, 20, 17]. The order of products in the output does not matter.

Solution

We can implement this ...