# Print all nodes less than a value x in a Min Heap.

Given a binary min heap and a value x, print all the binary heap nodes having value less than the given value x.

```Examples : Consider the below min heap as
common input two both below examples.
2
/
3        15
/         /
5       4  45  80
/      /
6   150 77 120

Input  : x = 15
Output : 2 3 5 6 4

Input  : x = 80
Output : 2 3 5 6 4 77 15 45
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

The idea is to do a preorder traversal of the give Binary heap. While doing preorder traversal, if the value of a node is greater than the given value x, we return to the previous recursive call. Because all children nodes in a min heap are greater than the parent node. Otherwise we print current node and recur for its children.

 `// A C++ program to print all values ` `// smaller than a given value in Binary ` `// Heap ` `#include ` `using` `namespace` `std; ` ` `  `// A class for Min Heap ` `class` `MinHeap ` `{ ` `    ``// pointer to array of elements in heap ` `    ``int` `*harr; ` ` `  `    ``// maximum possible size of min heap ` `    ``int` `capacity; ` `    ``int` `heap_size; ``// Current no. of elements. ` `public``: ` `    ``// Constructor ` `    ``MinHeap(``int` `capacity); ` ` `  `    ``// to heapify a subtree with root at ` `    ``// given index ` `    ``void` `MinHeapify(``int` `); ` ` `  `    ``int` `parent(``int` `i) { ``return` `(i-1)/2; } ` `    ``int` `left(``int` `i) { ``return` `(2*i + 1); } ` `    ``int` `right(``int` `i) { ``return` `(2*i + 2); } ` ` `  `    ``// Inserts a new key 'k' ` `    ``void` `insertKey(``int` `k); ` ` `  `    ``//Function to print all nodes smaller than k ` `    ``void` `printSmallerThan(``int` `k, ``int` `pos); ` `}; ` ` `  `// Function to print all elements smaller than k ` `void` `MinHeap::printSmallerThan(``int` `x, ``int` `pos=0) ` `{ ` `    ``/* Make sure item exists */` `    ``if` `(pos >= heap_size) ` `        ``return``; ` ` `  `    ``if` `(harr[pos] >= x) ` `    ``{ ` `        ``/* Skip this node and its descendants, ` `          ``as they are all >= x . */` `        ``return``; ` `    ``} ` ` `  `    ``cout << harr[pos] << ``" "``; ` ` `  `    ``printSmallerThan(x, left(pos)); ` `    ``printSmallerThan(x, right(pos)); ` `} ` ` `  `// Constructor: Builds a heap from a given ` `// array a[] of given size ` `MinHeap::MinHeap(``int` `cap) ` `{ ` `    ``heap_size = 0; ` `    ``capacity = cap; ` `    ``harr = ``new` `int``[cap]; ` `} ` ` `  `// Inserts a new key 'k' ` `void` `MinHeap::insertKey(``int` `k) ` `{ ` `    ``if` `(heap_size == capacity) ` `    ``{ ` `        ``cout << ````" Overflow: Could not insertKey "````; ` `        ``return``; ` `    ``} ` ` `  `    ``// First insert the new key at the end ` `    ``heap_size++; ` `    ``int` `i = heap_size - 1; ` `    ``harr[i] = k; ` ` `  `    ``// Fix the min heap property if it is violated ` `    ``while` `(i != 0 && harr[parent(i)] > harr[i]) ` `    ``{ ` `       ``swap(harr[i], harr[parent(i)]); ` `       ``i = parent(i); ` `    ``} ` `} ` ` `  `// A recursive method to heapify a subtree with ` `// root at given index. This method assumes that ` `// the subtrees are already heapified ` `void` `MinHeap::MinHeapify(``int` `i) ` `{ ` `    ``int` `l = left(i); ` `    ``int` `r = right(i); ` `    ``int` `smallest = i; ` `    ``if` `(l < heap_size && harr[l] < harr[i]) ` `        ``smallest = l; ` `    ``if` `(r < heap_size && harr[r] < harr[smallest]) ` `        ``smallest = r; ` `    ``if` `(smallest != i) ` `    ``{ ` `        ``swap(harr[i], harr[smallest]); ` `        ``MinHeapify(smallest); ` `    ``} ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `    ``MinHeap h(50); ` `    ``h.insertKey(3); ` `    ``h.insertKey(2); ` `    ``h.insertKey(15); ` `    ``h.insertKey(5); ` `    ``h.insertKey(4); ` `    ``h.insertKey(45); ` `    ``h.insertKey(80); ` `    ``h.insertKey(6); ` `    ``h.insertKey(150); ` `    ``h.insertKey(77); ` `    ``h.insertKey(120); ` ` `  `    ``// Print all nodes smaller than 100. ` `    ``int` `x = 100; ` `    ``h.printSmallerThan(x); ` ` `  `    ``return` `0; ` `} `

Output:

```2 3 5 6 4 77 15 45 80
```

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

Heap Heap

code

load comments