Given a Binary Tree consisting of 0s and 1s only, the task is to print the count of levels in the Binary Tree in which all the 1s are placed consecutively in a single group.
Examples:
Input: 0
/ \
1 0
/ \ / \
1 0 1 0
Output: 2
Explanation: In Levels 1 and 2, all the nodes with value 1 are placed consecutively.
Input: 0
/ \
1 0
/ \ \
1 1 0
/ \ \ / \
1 1 1 0 0
Output: 4
Explanation: In all the levels, nodes with value 1 are placed consecutively.
Approach: Follow the steps below to solve the problem:
- Perform Level Order Traversal using Queue.
- Traverse each level of the Binary Tree and consider following three variables:
- flag1: Sets to 1 after first occurrence of node with value 1.
- flag0: Sets to 1 after first occurrence of node with value 0 after occurrence of any node with value 1.
- flag2: Sets after first occurrence of node with value 1 after both flag0 and flag1 are set to 1.
- After traversing each level, check if flag1 is set to 1 and flag2 is 0. If found to be true, include that level in the count.
- Finally, print the count obtained.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;// A Binary Tree Nodestruct node { // Left Child struct node* left; int data; // Right Child struct node* right;};// Function to perform level order traversal// count levels with all 1s grouped togetherint countLevels(node* root){ if (root == NULL) return 0; int Count = 0; // Create an empty queue for // level order traversal queue<node*> q; // Stores front element of the queue node* curr; // Enqueue root and NULL node q.push(root); // Stores Nodes of // Current Level while (!q.empty()) { int n = q.size(); int flag0 = 0, flag1 = 0, flag2 = 0; while (n--) { // Stores first node of // the current level curr = q.front(); q.pop(); if (curr) { // If left child exists if (curr->left) // Push into the Queue q.push(curr->left); // If right child exists if (curr->right) // Push into the Queue q.push(curr->right); if (curr->data == 1) { // If current node is the first // node with value 1 if (!flag1) flag1 = 1; // If current node has value 1 // after occurrence of nodes // with value 0 following a // sequence of nodes with value 1 if (flag1 && flag0) flag2 = 1; } // If current node is the first node // with value 0 after a sequence // of nodes with value 1 if (curr->data == 0 && flag1) flag0 = 1; } } if (flag1 && !flag2) Count++; } return Count;}// Function to create a Tree Nodenode* newNode(int data){ node* temp = new node; temp->data = data; temp->left = NULL; temp->right = NULL; return temp;}// Driver Codeint main(){ node* root = newNode(0); root->left = newNode(0); root->right = newNode(1); root->left->left = newNode(0); root->left->right = newNode(1); root->right->left = newNode(1); root->right->right = newNode(0); cout << countLevels(root); return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{// A Binary Tree Nodestatic class node{ // Left Child node left; int data; // Right Child node right;};// Function to perform level order traversal// count levels with all 1s grouped togetherstatic int countLevels(node root){ if (root == null) return 0; int Count = 0; // Create an empty queue for // level order traversal Queue<node> q = new LinkedList<>(); // Stores front element of the queue node curr; // Enqueue root and null node q.add(root); // Stores Nodes of // Current Level while (!q.isEmpty()) { int n = q.size(); int flag0 = 0, flag1 = 0, flag2 = 0; while (n-- >0) { // Stores first node of // the current level curr = q.peek(); q.remove(); if (curr != null) { // If left child exists if (curr.left != null) // Push into the Queue q.add(curr.left); // If right child exists if (curr.right != null) // Push into the Queue q.add(curr.right); if (curr.data == 1) { // If current node is the first // node with value 1 if (flag1 == 0) flag1 = 1; // If current node has value 1 // after occurrence of nodes // with value 0 following a // sequence of nodes with value 1 if (flag1 > 0 && flag0 > 0) flag2 = 1; } // If current node is the first node // with value 0 after a sequence // of nodes with value 1 if (curr.data == 0 && flag1 > 0) flag0 = 1; } } if (flag1 > 0 && flag2 == 0) Count++; } return Count;}// Function to create a Tree Nodestatic node newNode(int data){ node temp = new node(); temp.data = data; temp.left = null; temp.right = null; return temp;}// Driver Codepublic static void main(String[] args){ node root = newNode(0); root.left = newNode(0); root.right = newNode(1); root.left.left = newNode(0); root.left.right = newNode(1); root.right.left = newNode(1); root.right.right = newNode(0); System.out.print(countLevels(root));}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to implement# the above approachfrom collections import deque# A Binary Tree Nodeclass node: def __init__(self): # Left Child self.left = None self.data = 0 # Right Child self.right = None# Function to perform level order traversal# count levels with all 1s grouped togetherdef countLevels(root): if (root == None): return 0 Count = 0 # Create an empty queue for # level order traversal q = deque() # Stores front element of the queue curr = node() # Enqueue root and None node q.append(root) # Stores Nodes of # Current Level while q: n = len(q) flag0 = 0 flag1 = 0 flag2 = 0 while (n): # Stores first node of # the current level curr = q[0] q.popleft() if (curr): # If left child exists if (curr.left): # Push into the Queue q.append(curr.left) # If right child exists if (curr.right): # Push into the Queue q.append(curr.right) if (curr.data == 1): # If current node is the first # node with value 1 if (not flag1): flag1 = 1 # If current node has value 1 # after occurrence of nodes # with value 0 following a # sequence of nodes with value 1 if (flag1 and flag0): flag2 = 1 # If current node is the first node # with value 0 after a sequence # of nodes with value 1 if (curr.data == 0 and flag1): flag0 = 1 n -= 1 if (flag1 and not flag2): Count += 1 return Count# Function to create a Tree Nodedef newNode(data): temp = node() temp.data = data temp.left = None temp.right = None return temp# Driver Codeif __name__ == "__main__": root = newNode(0) root.left = newNode(0) root.right = newNode(1) root.left.left = newNode(0) root.left.right = newNode(1) root.right.left = newNode(1) root.right.right = newNode(0) print(countLevels(root))# This code is contributed by sanjeev2552 |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// A Binary Tree Nodeclass node{ // Left Child public node left; public int data; // Right Child public node right;};// Function to perform level order traversal// count levels with all 1s grouped togetherstatic int countLevels(node root){ if (root == null) return 0; int Count = 0; // Create an empty queue for // level order traversal Queue<node> q = new Queue<node>(); // Stores front element of the queue node curr; // Enqueue root and null node q.Enqueue(root); // Stores Nodes of // Current Level while (q.Count != 0) { int n = q.Count; int flag0 = 0, flag1 = 0, flag2 = 0; while (n-- >0) { // Stores first node of // the current level curr = q.Peek(); q.Dequeue(); if (curr != null) { // If left child exists if (curr.left != null) // Push into the Queue q.Enqueue(curr.left); // If right child exists if (curr.right != null) // Push into the Queue q.Enqueue(curr.right); if (curr.data == 1) { // If current node is the first // node with value 1 if (flag1 == 0) flag1 = 1; // If current node has value 1 // after occurrence of nodes // with value 0 following a // sequence of nodes with value 1 if (flag1 > 0 && flag0 > 0) flag2 = 1; } // If current node is the first node // with value 0 after a sequence // of nodes with value 1 if (curr.data == 0 && flag1 > 0) flag0 = 1; } } if (flag1 > 0 && flag2 == 0) Count++; } return Count;}// Function to create a Tree Nodestatic node newNode(int data){ node temp = new node(); temp.data = data; temp.left = null; temp.right = null; return temp;}// Driver Codepublic static void Main(String[] args){ node root = newNode(0); root.left = newNode(0); root.right = newNode(1); root.left.left = newNode(0); root.left.right = newNode(1); root.right.left = newNode(1); root.right.right = newNode(0); Console.Write(countLevels(root));}}// This code is contributed by 29AjayKumar |
Javascript
<script> // JavaScript program for above approach // A Binary Tree Node class node { constructor(data) { this.left = null; this.right = null; this.data = data; } } // Function to create a Tree Node function newNode(data) { let temp = new node(data); return temp; } // Function to perform level order traversal // count levels with all 1s grouped together function countLevels(root) { if (root == null) return 0; let Count = 0; // Create an empty queue for // level order traversal let q = []; // Stores front element of the queue let curr; // Enqueue root and null node q.push(root); // Stores Nodes of // Current Level while (q.length > 0) { let n = q.length; let flag0 = 0, flag1 = 0, flag2 = 0; while (n-- >0) { // Stores first node of // the current level curr = q[0]; q.shift(); if (curr != null) { // If left child exists if (curr.left != null) // Push into the Queue q.push(curr.left); // If right child exists if (curr.right != null) // Push into the Queue q.push(curr.right); if (curr.data == 1) { // If current node is the first // node with value 1 if (flag1 == 0) flag1 = 1; // If current node has value 1 // after occurrence of nodes // with value 0 following a // sequence of nodes with value 1 if (flag1 > 0 && flag0 > 0) flag2 = 1; } // If current node is the first node // with value 0 after a sequence // of nodes with value 1 if (curr.data == 0 && flag1 > 0) flag0 = 1; } } if (flag1 > 0 && flag2 == 0) Count++; } return Count; } let root = newNode(0); root.left = newNode(0); root.right = newNode(1); root.left.left = newNode(0); root.left.right = newNode(1); root.right.left = newNode(1); root.right.right = newNode(0); document.write(countLevels(root)); </script> |
Output:
2
Time Complexity: O(N)
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!
