Count levels in a Binary Tree consisting of nodes valued 1 grouped together

0 0 8 minutes read

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:
1. flag1: Sets to 1 after first occurrence of node with value 1.
2. flag0: Sets to 1 after first occurrence of node with value 0 after occurrence of any node with value 1.
3. 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 Node
struct 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 together
int 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 Node
node* newNode(int data)
{
    node* temp = new node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
 
// Driver Code
int 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 approach
import java.util.*;
class GFG
{
 
// A Binary Tree Node
static class node
{
 
    // Left Child
    node left;
    int data;
 
    // Right Child
    node right;
};
 
// Function to perform level order traversal
// count levels with all 1s grouped together
static 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 Node
static node newNode(int data)
{
    node temp = new node();
    temp.data = data;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
// Driver Code
public 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 approach
from collections import deque
 
# A Binary Tree Node
class 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 together
def 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 Node
def newNode(data):
 
    temp = node()
    temp.data = data
    temp.left = None
    temp.right = None
    return temp
 
# Driver Code
if __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 approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
// A Binary Tree Node
class 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 together
static 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 Node
static node newNode(int data)
{
    node temp = new node();
    temp.data = data;
    temp.left = null;
    temp.right = null;
    return temp;
}
 
// Driver Code
public 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:

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 zambiatek!