Approach
The solution approach for the given problem is quite an interesting one. As we all know, a min-heap data structure is one in which the key at the root node must be smaller than or equal to the keys at all of its descendants. We start by doing a pre-order traversal of the min-heap. If we find a node greater than the given value of the x, we return to a previous recursive call. Otherwise, we simply print the node.
Algorithm
1. We begin by traversing the given Binary heap by preorder traversal.
2. We return to the previous recursive call if the value of a node is larger than the provided value x.
3. If not, we print the node.
4. We then repeat the same process for its children nodes.
Implementation
#include <bits/stdc++.h>
using namespace std;
// defining class for Min Heap
class Min_Heap
{
int* harr;
int capacity;
int heapSize;
public:
// Constructor function
Min_Heap(int capacity);
void Min_Heapify(int);
int root(int index) {
return (index - 1) / 2;
}
int left(int index) {
return (2 * index + 1);
}
int right(int index) {
return (2 * index + 2);
}
void insert(int k);
void printSmall(int k, int pos);
};
// Function to print every element lesser than k
void Min_Heap::printSmall(int x, int pos = 0)
{
if (pos >= heapSize)
return;
if (harr[pos] >= x) {
return;
}
cout << harr[pos] << " ";
printSmall(x, left(pos));
printSmall(x, right(pos));
}
// Constructor function
Min_Heap::Min_Heap(int cap)
{
heapSize = 0;
capacity = cap;
harr = new int[cap];
}
// Function for inserting a new key 'k'
void Min_Heap::insert(int k)
{
if (heapSize == capacity) {
cout << "\nOverflow: Could not insert\n";
return;
}
heapSize++;
int i = heapSize - 1;
harr[i] = k;
while (i != 0 && harr[root(i)] > harr[i]) {
swap(harr[i], harr[root(i)]);
i = root(i);
}
}
// A recursive method for heapifing a subtree with
// root at the given index.
void Min_Heap::Min_Heapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heapSize && harr[l] < harr[i])
smallest = l;
if (r < heapSize && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(harr[i], harr[smallest]);
Min_Heapify(smallest);
}
}
// Driver program
int main()
{
Min_Heap h(50);
h.insert(3);
h.insert(2);
h.insert(15);
h.insert(5);
h.insert(4);
h.insert(45);
h.insert(80);
h.insert(6);
h.insert(150);
h.insert(77);
h.insert(120);
int x = 100;
h.printSmall(x);
return 0;
}
You can also try this code with Online C++ Compiler
Output
2 3 5 6 4 15
Time Complexity
The Time complexity of the given approach is O(n) because the call stack is accessed n times, where n is the number of elements.
Space Complexity
The Space complexity of the above approach is O(1), as no other data structures are used for memory management.
Frequently Asked Questions
What are Tries?
Tries are data structures that stores a set of strings as a sorted tree. Each node has the same number of pointers as to the number of alphabet characters.
What is the file bits/stdc++.h?
The header bits/stdc++.h includes all standard libraries. This is useful when you don't want to waste time including many header files.
What are the uses of a Pre-order traversal?
Preorder traversal is used to duplicate the tree. Preorder traversal is also utilized on an expression tree to obtain the prefix expression.
Conclusion
In this blog, we discussed a coding problem in which we printed all the elements smaller than a given value in a given min-heap. We discussed the time and space complexity of the approach as well.
Cheers, you have reached the end. Hope you liked the blog and it has added some knowledge to your life. Please look at these similar topics to learn more: Implementation of Heap, Binary Heap, Build Heap, Min Heap.
Recommended Problems:
Refer to our Coding Ninjas Studio Guided Path to learn Data Structures and Algorithms, Competitive Programming, JavaScript, System Design, and even more! You can also check out the mock test series and participate in the contests hosted by Coding Ninjas Studio! But say you're just starting and want to learn about questions posed by tech titans like Amazon, Microsoft, Uber, and so on. In such a case, for placement preparations, you can also look at the problems, interview experiences, and interview bundle.
You should also consider our premium courses to offer your career advantage over others!
Please upvote our blogs if you find them useful and exciting!
Happy Coding!
34+ registered 
