Given a Binary Tree, the task is for each level is to print the total number of nodes from all lower levels which are less than or equal to every node present at that level.
Examples:
Input: Below is the given tree:
4
/ \
3 5
/ \ / \
10 2 3 1Output: 4 3 0
Explanation:
Nodes in level 1 has 4 nodes as (3) in level 2 and (2, 3, 1) in level 3.
Nodes in level 2 has 3 nodes as (2, 3, 1) in level 3.
Nodes in level 3 does not have any level left below it.Input: Below is the given tree:
4
/ \
7 9
/ / \
1 3 1
Output: 3 3 0
Approach: Follow the steps below to solve the problem:
- Calculate the minimum value at every level using Level Order Traversal.
- Perform Post Order Traversal on the tree and check for every node whether nodes computed in step 1 are greater than or equal to the node. If found to be true, increment count by one at that level, providing that particular level has the node present in the level below it whose value is less than or equal to all the nodes present at that level.
- Print the final array which gives the number of nodes for that level.
Below is the implementation of the above approach:
C++
// C++ program of the// above approach#include <bits/stdc++.h>using namespace std;// Stores the nodes to be deletedunordered_map<int, bool> mp;// Structure of a Tree nodestruct Node { int key; struct Node *left, *right;};// Function to create a new nodeNode* newNode(int key){ Node* temp = new Node; temp->key = key; temp->left = temp->right = NULL; return (temp);}// Function to find the min value// of node for each levelvoid calculateMin(Node* root, vector<int>& levelMin){ queue<Node*> qt; qt.push(root); // Count is used to differentiate // each level of the tree int count = 1; int min_v = INT_MAX; while (!qt.empty()) { Node* temp = qt.front(); min_v = min(min_v, temp->key); qt.pop(); if (temp->left) { qt.push(temp->left); } if (temp->right) { qt.push(temp->right); } count--; if (count == 0) { levelMin.push_back(min_v); min_v = INT_MAX; count = qt.size(); } }}// Function to check whether the nodes in// the level below it are smaller// by performing post order traversalvoid findNodes(Node* root, vector<int>& levelMin, vector<int>& levelResult, int level){ if (root == NULL) return; // Traverse the left subtree findNodes(root->left, levelMin, levelResult, level + 1); // Traverse right subtree findNodes(root->right, levelMin, levelResult, level + 1); // Check from minimum values // computed at each level for (int i = 0; i < level; i++) { if (root->key <= levelMin[i]) { levelResult[i] += 1; } }}// Function to print count of// nodes from all lower levels// having values less than the// the nodes in the current levelvoid printNodes(Node* root){ vector<int> levelMin; calculateMin(root, levelMin); // Stores the number of levels int numLevels = levelMin.size(); // Stores the required count // of nodes for each level vector<int> levelResult(numLevels, 0); findNodes(root, levelMin, levelResult, 0); for (int i = 0; i < numLevels; i++) { cout << levelResult[i] << " "; }}// Driver Codeint main(){ /* 4 / \ 3 5 / \ / \ 10 2 3 1 */ Node* root = newNode(4); root->left = newNode(3); root->right = newNode(5); root->right->left = newNode(3); root->right->right = newNode(1); root->left->left = newNode(10); root->left->right = newNode(2); printNodes(root);} |
Java
// Java program of the// above approachimport java.util.*;class GFG{// Stores the nodes to be deletedstatic Map<Integer, Boolean> mp = new HashMap<Integer, Boolean>(); // Structure of a Tree nodestatic class Node { int key; Node left, right;};// Function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);}// Function to find the min value// of node for each levelstatic void calculateMin(Node root, Vector<Integer> levelMin){ Queue<Node> qt = new LinkedList<>(); qt.add(root); // Count is used to differentiate // each level of the tree int count = 1; int min_v = Integer.MAX_VALUE; while (!qt.isEmpty()) { Node temp = qt.peek(); min_v = Math.min(min_v, temp.key); qt.remove(); if (temp.left != null) { qt.add(temp.left); } if (temp.right != null) { qt.add(temp.right); } count--; if (count == 0) { levelMin.add(min_v); min_v = Integer.MAX_VALUE; count = qt.size(); } }}// Function to check whether the nodes in// the level below it are smaller// by performing post order traversalstatic void findNodes(Node root, Vector<Integer> levelMin, int []levelResult, int level){ if (root == null) return; // Traverse the left subtree findNodes(root.left, levelMin, levelResult, level + 1); // Traverse right subtree findNodes(root.right, levelMin, levelResult, level + 1); // Check from minimum values // computed at each level for (int i = 0; i < level; i++) { if (root.key <= levelMin.get(i)) { levelResult[i] += 1; } }}// Function to print count of// nodes from all lower levels// having values less than the// the nodes in the current levelstatic void printNodes(Node root){ Vector<Integer> levelMin = new Vector<Integer>(); calculateMin(root, levelMin); // Stores the number of levels int numLevels = levelMin.size(); // Stores the required count // of nodes for each level int []levelResult = new int[numLevels]; findNodes(root, levelMin, levelResult, 0); for (int i = 0; i < numLevels; i++) { System.out.print(levelResult[i] + " "); }}// Driver Codepublic static void main(String[] args){ /* 4 / \ 3 5 / \ / \ 10 2 3 1 */ Node root = newNode(4); root.left = newNode(3); root.right = newNode(5); root.right.left = newNode(3); root.right.right = newNode(1); root.left.left = newNode(10); root.left.right = newNode(2); printNodes(root);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program of the# above approachfrom collections import dequefrom sys import maxsize as INT_MAX# Stores the nodes to be deletedmp = dict()# Structure of a Tree nodeclass Node: def __init__(self, key): self.key = key self.left = None self.right = None# Function to find the min value# of node for each leveldef calculateMin(root: Node, levelMin: list) -> None: qt = deque() qt.append(root) # Count is used to differentiate # each level of the tree count = 1 min_v = INT_MAX while (qt): temp = qt.popleft() min_v = min(min_v, temp.key) if (temp.left): qt.append(temp.left) if (temp.right): qt.append(temp.right) count -= 1 if (count == 0): levelMin.append(min_v) min_v = INT_MAX count = len(qt)# Function to check whether the nodes in# the level below it are smaller# by performing post order traversaldef findNodes(root: Node, levelMin: list, levelResult: list, level: int) -> None: if (root == None): return # Traverse the left subtree findNodes(root.left, levelMin, levelResult, level + 1) # Traverse right subtree findNodes(root.right, levelMin, levelResult, level + 1) # Check from minimum values # computed at each level for i in range(level): if (root.key <= levelMin[i]): levelResult[i] += 1# Function to print count of# nodes from all lower levels# having values less than the# the nodes in the current leveldef printNodes(root: Node) -> None: levelMin = [] calculateMin(root, levelMin) # Stores the number of levels numLevels = len(levelMin) # Stores the required count # of nodes for each level levelResult = [0] * numLevels findNodes(root, levelMin, levelResult, 0) for i in range(numLevels): print(levelResult[i], end = " ")# Driver Codeif __name__ == "__main__": ''' 4 / \ 3 5 / \ / \ 10 2 3 1 ''' root = Node(4) root.left = Node(3) root.right = Node(5) root.right.left = Node(3) root.right.right = Node(1) root.left.left = Node(10) root.left.right = Node(2) printNodes(root)# This code is contributed by sanjeev2552 |
C#
// C# program of the// above approachusing System;using System.Collections.Generic;class GFG{// Stores the nodes to be deletedstatic Dictionary<int, Boolean> mp = new Dictionary<int, Boolean>();// Structure of a Tree nodeclass Node { public int key; public Node left, right;};// Function to create a new nodestatic Node newNode(int key){ Node temp = new Node(); temp.key = key; temp.left = temp.right = null; return (temp);}// Function to find the min value// of node for each levelstatic void calculateMin(Node root, List<int> levelMin){ Queue<Node> qt = new Queue<Node>(); qt.Enqueue(root); // Count is used to differentiate // each level of the tree int count = 1; int min_v = int.MaxValue; while (qt.Count != 0) { Node temp = qt.Peek(); min_v = Math.Min(min_v, temp.key); qt.Dequeue(); if (temp.left != null) { qt.Enqueue(temp.left); } if (temp.right != null) { qt.Enqueue(temp.right); } count--; if (count == 0) { levelMin.Add(min_v); min_v = int.MaxValue; count = qt.Count; } }}// Function to check whether the nodes in// the level below it are smaller// by performing post order traversalstatic void findNodes(Node root, List<int> levelMin, int []levelResult, int level){ if (root == null) return; // Traverse the left subtree findNodes(root.left, levelMin, levelResult, level + 1); // Traverse right subtree findNodes(root.right, levelMin, levelResult, level + 1); // Check from minimum values // computed at each level for(int i = 0; i < level; i++) { if (root.key <= levelMin[i]) { levelResult[i] += 1; } }}// Function to print count of// nodes from all lower levels// having values less than the// the nodes in the current levelstatic void printNodes(Node root){ List<int> levelMin = new List<int>(); calculateMin(root, levelMin); // Stores the number of levels int numLevels = levelMin.Count; // Stores the required count // of nodes for each level int []levelResult = new int[numLevels]; findNodes(root, levelMin, levelResult, 0); for(int i = 0; i < numLevels; i++) { Console.Write(levelResult[i] + " "); }}// Driver Codepublic static void Main(String[] args){/* 4 / \ 3 5 / \ / \ 10 2 3 1 */ Node root = newNode(4); root.left = newNode(3); root.right = newNode(5); root.right.left = newNode(3); root.right.right = newNode(1); root.left.left = newNode(10); root.left.right = newNode(2); printNodes(root);}}// This code is contributed by Amit Katiyar |
Javascript
<script> // JavaScript program for the above approach // Structure of a Tree node class Node { constructor(key) { this.left = null; this.right = null; this.key = key; } } // Function to create a new node function newNode(key) { let temp = new Node(key); return (temp); } // Function to find the min value // of node for each level function calculateMin(root, levelMin) { let qt = []; qt.push(root); // Count is used to differentiate // each level of the tree let count = 1; let min_v = Number.MAX_VALUE; while (qt.length > 0) { let temp = qt[0]; min_v = Math.min(min_v, temp.key); qt.shift(); if (temp.left != null) { qt.push(temp.left); } if (temp.right != null) { qt.push(temp.right); } count--; if (count == 0) { levelMin.push(min_v); min_v = Number.MAX_VALUE; count = qt.length; } } } // Function to check whether the nodes in // the level below it are smaller // by performing post order traversal function findNodes(root, levelMin, levelResult, level) { if (root == null) return; // Traverse the left subtree findNodes(root.left, levelMin, levelResult, level + 1); // Traverse right subtree findNodes(root.right, levelMin, levelResult, level + 1); // Check from minimum values // computed at each level for (let i = 0; i < level; i++) { if (root.key <= levelMin[i]) { levelResult[i] += 1; } } } // Function to print count of // nodes from all lower levels // having values less than the // the nodes in the current level function printNodes(root) { let levelMin = []; calculateMin(root, levelMin); // Stores the number of levels let numLevels = levelMin.length; // Stores the required count // of nodes for each level let levelResult = new Array(numLevels); levelResult.fill(0); findNodes(root, levelMin, levelResult, 0); for (let i = 0; i < levelResult.length; i++) { document.write(levelResult[i] + " "); } } /* 4 / \ 3 5 / \ / \ 10 2 3 1 */ let root = newNode(4); root.left = newNode(3); root.right = newNode(5); root.right.left = newNode(3); root.right.right = newNode(1); root.left.left = newNode(10); root.left.right = newNode(2); printNodes(root); </script> |
Output:
4 3 0
Time Complexity: O(N2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
