# Smallest value in each level of Binary Tree

Given a binary tree containing n nodes, the task is to print minimum element in each level of binary tree.

Examples:

```Input :
7
/
6       5
/      /
4  3     2  1

Output :
Every level minimum is
level 0 min is = 7
level 1 min is = 5
level 2 min is = 1

Input :
7
/
16       1
/
4   13

Output :
Every level minimum is
level 0 min is = 7
level 1 min is = 1
level 2 min is = 4
```

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

Method 1: Using In-order traversal
Approach:- The idea is to recursively traverse tree in a in-order fashion. Root is considered to be at zeroth level. First find the height of tree and store it into res. res array store every smallest element in each level of binary tree.

Below is the implementation to find smallest value on each level of Binary Tree.

 `// CPP program to print smallest element ` `// in each level of binary tree. ` `#include ` `#include ` `#define INT_MAX 10e6 ` `using` `namespace` `std; ` ` `  `// A Binary Tree Node ` `struct` `Node { ` `    ``int` `data; ` `    ``struct` `Node *left, *right; ` `}; ` ` `  `// return height of tree ` `int` `heightoftree(Node* root) ` `{ ` ` `  `    ``if` `(root == NULL) ` `        ``return` `0; ` ` `  `    ``int` `left = heightoftree(root->left); ` `    ``int` `right = heightoftree(root->right); ` ` `  `    ``return` `((left > right ? left : right) + 1); ` `} ` ` `  `// Inorder Traversal ` `// Search minimum element in each level and  ` `// store it into vector array. ` `void` `printPerLevelMinimum(Node* root,  ` `                  ``vector<``int``>& res, ``int` `level) ` `{ ` `     `  `    ``if` `(root != NULL) { ` ` `  `        ``printPerLevelMinimum(root->left, ` `                              ``res, level + 1); ` ` `  `        ``if` `(root->data < res[level]) ` `            ``res[level] = root->data; ` ` `  `        ``printPerLevelMinimum(root->right,  ` `                              ``res, level + 1); ` `    ``} ` `} ` ` `  `void` `perLevelMinimumUtility(Node* root) ` `{ ` `     `  `    ``// height of tree for the size of  ` `    ``// vector array ` `    ``int` `n = heightoftree(root), i; ` ` `  `    ``// vector for store all minimum of  ` `    ``// every level ` `    ``vector<``int``> res(n, INT_MAX); ` ` `  `    ``// save every level minimum using  ` `    ``// inorder traversal ` `    ``printPerLevelMinimum(root, res, 0); ` ` `  `    ``// print every level minimum ` `    ``cout << ````"Every level minimum is "````; ` `    ``for` `(i = 0; i < n; i++) { ` `        ``cout << ``"level "` `<< i <<``" min is = "` `                            ``<< res[i] << ````" "````; ` `    ``} ` `} ` ` `  `// Utility function to create a new tree node ` `Node* newNode(``int` `data) ` `{ ` `    ``Node* temp = ``new` `Node; ` `    ``temp->data = data; ` `    ``temp->left = temp->right = NULL; ` ` `  `    ``return` `temp; ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` ` `  `    ``// Let us create binary tree shown  ` `    ``// in above diagram ` `    ``Node* root = newNode(7); ` `    ``root->left = newNode(6); ` `    ``root->right = newNode(5); ` `    ``root->left->left = newNode(4); ` `    ``root->left->right = newNode(3); ` `    ``root->right->left = newNode(2); ` `    ``root->right->right = newNode(1); ` ` `  `    ``/*       7 ` `         ``/  ` `        ``6     5 ` `       ``/      / ` `      ``4   3 2   1         */` `    ``perLevelMinimumUtility(root); ` ` `  `    ``return` `0; ` `} `

Output:-

```Every level minimum is
level 0 min is = 7
level 1 min is = 5
level 2 min is = 1
```

Method 2: Using level order Traversal
Approach:- The idea is to perform iterative level order traversal of the binary tree using queue. While traversing keep min variable which stores the minimum element of the current level of the tree being processed. When the level is completely traversed, print that min value.

## C++

 `// CPP program to print minimum element ` `// in each level of binary tree. ` `#include ` `#include ` `#include ` `#define INT_MAX 10e6 ` `using` `namespace` `std; ` ` `  `// A Binary Tree Node ` `struct` `Node { ` `    ``int` `data; ` `    ``struct` `Node *left, *right; ` `}; ` ` `  `// return height of tree ` `int` `heightoftree(Node* root) ` `{ ` ` `  `    ``if` `(root == NULL) ` `        ``return` `0; ` ` `  `    ``int` `left = heightoftree(root->left); ` `    ``int` `right = heightoftree(root->right); ` ` `  `    ``return` `((left > right ? left : right) + 1); ` `} ` ` `  `// Iterative method to find every level ` `// minimum element of Binary Tree ` `void` `printPerLevelMinimum(Node* root) ` `{ ` ` `  `    ``// Base Case ` `    ``if` `(root == NULL) ` `        ``return` `; ` ` `  `    ``// Create an empty queue for  ` `    ``// level order traversal ` `    ``queue q; ` ` `  `    ``// push the root for Change the level ` `    ``q.push(root); ` ` `  `    ``// for go level by level ` `    ``q.push(NULL); ` ` `  `    ``int` `min = INT_MAX; ` `    ``// for check the level ` `    ``int` `level = 0; ` ` `  `    ``while` `(q.empty() == ``false``) { ` ` `  `        ``// Get top of queue ` `        ``Node* node = q.front(); ` `        ``q.pop(); ` ` `  `        ``// if node == NULL (Means this is  ` `        ``// boundary between two levels) ` `        ``if` `(node == NULL) { ` ` `  `            ``cout << ``"level "` `<< level <<  ` `             ``" min is = "` `<< min << ````" "````; ` ` `  `            ``// here queue is empty represent ` `            ``// no element in the actual ` `            ``// queue ` `            ``if` `(q.empty()) ` `                ``break``; ` ` `  `            ``q.push(NULL); ` ` `  `            ``// increment level ` `            ``level++; ` ` `  `            ``// Reset min for next level  ` `            ``// minimum value ` `            ``min = INT_MAX; ` ` `  `            ``continue``; ` `        ``} ` ` `  `        ``// get Minimum in every level ` `        ``if` `(min > node->data) ` `            ``min = node->data; ` ` `  `        ``/* Enqueue left child */` `        ``if` `(node->left != NULL) { ` `            ``q.push(node->left); ` `        ``} ` ` `  `        ``/*Enqueue right child */` `        ``if` `(node->right != NULL) { ` `            ``q.push(node->right); ` `        ``} ` `    ``} ` `} ` ` `  `// Utility function to create a  ` `// new tree node ` `Node* newNode(``int` `data) ` `{ ` `     `  `    ``Node* temp = ``new` `Node; ` `    ``temp->data = data; ` `    ``temp->left = temp->right = NULL; ` `     `  `    ``return` `temp; ` `} ` ` `  `// Driver program to test above functions ` `int` `main() ` `{ ` `     `  `    ``// Let us create binary tree shown  ` `    ``// in above diagram ` `    ``Node* root = newNode(7); ` `    ``root->left = newNode(6); ` `    ``root->right = newNode(5); ` `    ``root->left->left = newNode(4); ` `    ``root->left->right = newNode(3); ` `    ``root->right->left = newNode(2); ` `    ``root->right->right = newNode(1); ` ` `  `    ``/*      7 ` `        ``/  ` `       ``6    5 ` `      ``/   / ` `     ``4  3 2   1         */` ` `  `    ``cout << ``"Every Level minimum is"` `        ``<< ````" "````; ` `         `  `    ``printPerLevelMinimum(root); ` `     `  `    ``return` `0; ` `} `

## Python3

# Python3 program to prminimum element
# in each level of binary tree.

# Importing Queue
from queue import Queue

# Utility class to create a
# new tree node
class newNode:
def __init__(self, data):
self.data = data
self.left = self.right = None

# return height of tree p
def heightoftree(root):

if (root == None):
return 0

left = heightoftree(root.left)
right = heightoftree(root.right)
if left > right:
return left + 1
else:
return right + 1

# Iterative method to find every level
# minimum element of Binary Tree
def printPerLevelMinimum(root):

# Base Case
if (root == None):
return

# Create an empty queue for
# level order traversal
q = Queue()

# put the root for Change the level
q.put(root)

# for go level by level
q.put(None)

Min = 9999999999999

# for check the level
level = 0

while (q.empty() == False):

# Get get of queue
node = q.queue
q.get()

# if node == None (Means this is
# boundary between two levels)
if (node == None):

print(“level”, level, “min is =”, Min)

# here queue is empty represent
# no element in the actual
# queue
if (q.empty()):
break

q.put(None)

# increment level
level += 1

# Reset min for next level
# minimum value
Min = 999999999999

continue

# get Minimum in every level
if (Min > node.data):
Min = node.data

# Enqueue left child
if (node.left != None):
q.put(node.left)

#Enqueue right child
if (node.right != None):
q.put(node.right)

# Driver Code
if __name__ == ‘__main__’:

# Let us create binary tree shown
# in above diagram
root = newNode(7)
root.left = newNode(6)
root.right = newNode(5)
root.left.left = newNode(4)
root.left.right = newNode(3)
root.right.left = newNode(2)
root.right.right = newNode(1)

# 7
# /
# 6 5
# / /
# 4 3 2 1
print(“Every Level minimum is”)

printPerLevelMinimum(root)

# This code is contributed by PranchalK

Output:

```Every level minimum is
level 0 min is = 7
level 1 min is = 5
level 2 min is = 1
```

## tags:

Tree tree-level-order Tree