Number of levels having balanced parentheses in a Binary Tree
Given a Binary Tree consisting only β(β and β)β a level is considered to be balanced if the nodes of the level having parenthesis are balanced from left to right. The task is to count the total number of balanced levels in a binary tree.
Examples:
Input: (
/ \
( )
/ \ \
( ) (
/ \ \ \
( ( ) )Output: 2
Explanation:
In Level 2 and 4, the parenthesis are balanced.Input: )
/ \
( )
/ \
( )
/
(Output: 2
Explanation:
In Level 2 and 3, the parenthesis are balanced.
Approach: Follow the steps below to solve the problem:
- Initialize a queue to perform Lever Order traversal on a given Binary Tree.
- Initialize a stack to check for each level, whether the parentheses are balanced or not.
- Traverse each level one by one and perform the following steps:
- If the current node value is β(β, push it into the stack.
- If the current node value is β)β, then check whether the stack is empty or not. If non-empty and top of the stack is β(β, then pop it from the stack.
- Otherwise, conclude that the parentheses are not balanced.
- And at the end of the traversal, if the stack is found to be empty, then conclude that the parentheses are balanced. Otherwise, conclude that the parentheses are not balanced.
Below is the implementation of the above approach:
C++
// C++ program for Number of levels having balanced // parentheses in a Binary Tree #include <bits/stdc++.h> using namespace std; // Class containing left and // right child of current // node and key value struct Node { Node* left; Node* right; int key; Node( int item) { key = item; this ->left = nullptr; this ->right = nullptr; } }; // Root of Binary Tree Node* root = nullptr; // Function to count levels in the // Binary Tree having balanced parentheses int countbal(Node* root) { // Stores nodes of each level queue<Node*> que; que.push(root); // Stores required count of // levels with balanced parentheses int ans = 0; // Iterate until false while ( true ) { // Stores parentheses stack< char > stk; bool flag = true ; int len = que.size(); // If length is false if (len == 0) { break ; } while (len > 0) { // Pop 0 from queue // and store it in temp Node* temp = que.front(); que.pop(); // Check if temp.key // is equal to '(' if (temp->key == '(' ) { // push '(' into stack stk.push( '(' ); } else { // If stk is not empty and the // last element in the stack is '( if (stk.size() > 0 && stk.top() == '(' ) { // Pop from stack stk.pop(); } else { // Mark flag as False flag = false ; } } // If tmp.left is True if (temp->left != nullptr) { // push temp.left into queue que.push(temp->left); } // If tmp.right is True if (temp->right != nullptr) { // push temp.right into queue que.push(temp->right); } // Decrement length by 1 len--; } // If flag is True // and stk is False if (flag && stk.size() > 0) { ans += 1; } } return ans; } int main() { /*create root*/ // creating all its child root = new Node( '(' ); root->left = new Node( '(' ); root->right = new Node( ')' ); root->left->left = new Node( '(' ); root->left->right = new Node( ')' ); root->right->right = new Node( '(' ); root->left->left->left = new Node( '(' ); root->left->left->right = new Node( '(' ); root->right->right->left = new Node( ')' ); root->right->right->right = new Node( ')' ); // function call and ans print cout << countbal(root); return 0; } // This code is contributed by suresh07. |
Java
// Java program for Number of levels having balanced // parentheses in a Binary Tree import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /* Class containing left and right child of current node and key value*/ class Node { char key; Node left, right; public Node( char item) { key = item; left = right = null ; } } // A Java program to introduce Binary Tree class BinaryTree { // Root of Binary Tree Node root; // Constructors BinaryTree( char key) { root = new Node(key); } BinaryTree() { root = null ; } // Function to count levels in the // Binary Tree having balanced parentheses public static int countbal(Node root) { // Stores nodes of each level Queue<Node> que = new LinkedList<>(); que.add(root); // Stores required count of // levels with balanced parentheses int ans = 0 ; // Iterate until false while ( true ) { // Stores parentheses Stack<Character> stk = new Stack<>(); boolean flag = true ; int len = que.size(); // If length is false if (len == 0 ) { break ; } while (len > 0 ) { // Pop 0 from queue // and store it in temp Node temp = que.remove(); // Check if temp.key // is equal to '(' if (temp.key == '(' ) { // push '(' into stack stk.push( '(' ); } else { // If stk is not empty and the // last element in the stack is '( if (stk.size() > 0 && stk.peek() == '(' ) { // Pop from stack stk.pop(); } else { // Mark flag as False flag = false ; } } // If tmp.left is True if (temp.left != null ) { // push temp.left into queue que.add(temp.left); } // If tmp.right is True if (temp.right != null ) { // push temp.right into queue que.add(temp.right); } // Decrement length by 1 len--; } // If flag is True // and stk is False if (flag && stk.size() > 0 ) { ans += 1 ; } } return ans; } // Driver code public static void main(String[] args) { BinaryTree tree = new BinaryTree(); /*create root*/ // creating all its child tree.root = new Node( '(' ); tree.root.left = new Node( '(' ); tree.root.right = new Node( ')' ); tree.root.left.left = new Node( '(' ); tree.root.left.right = new Node( ')' ); tree.root.right.right = new Node( '(' ); tree.root.left.left.left = new Node( '(' ); tree.root.left.left.right = new Node( '(' ); tree.root.right.right.left = new Node( ')' ); tree.root.right.right.right = new Node( ')' ); // function call and ans print System.out.println(countbal(tree.root)); } } // This code is contributed by adity7409. |
Python3
# Python Code for above approach # Structure of a Tree Node class TreeNode: def __init__( self , val = '', left = None , right = None ): self .val = val self .left = left self .right = right # Function to count levels in the # Binary Tree having balanced parentheses def countBal(root): # Stores nodes of each level que = [root] # Stores required count of # levels with balanced parentheses ans = 0 # Iterate until false while True : # Stores parentheses stk = [] flag = True length = len (que) # If length is false if not length: break while length: # Pop 0 from queue # and store it in temp temp = que.pop( 0 ) # Check if temp.val # is equal to '(' if temp.val = = '(' : # Append '(' into stack stk.append( '(' ) else : # If stk is not empty and the # last element in the stack is '(' if stk and stk[ - 1 ] = = '(' : # Pop from stack stk.pop() else : # Mark flag as False flag = False # If tmp.left is True if temp.left: # Append temp.left into queue que.append(temp.left) # If tmp.right is True if temp.right: # Append temp.right into queue que.append(temp.right) # Decrement length by 1 length - = 1 # If flag is True # and stk is False if flag and not stk: ans + = 1 # Return ans return ans # Driver Code root = TreeNode( '(' ) root.left = TreeNode( '(' ) root.right = TreeNode( ')' ) root.left.left = TreeNode( '(' ) root.left.right = TreeNode( ')' ) root.right.right = TreeNode( '(' ) root.left.left.left = TreeNode( '(' ) root.left.left.right = TreeNode( '(' ) root.right.right.left = TreeNode( ')' ) root.right.right.right = TreeNode( ')' ) print (countBal(root)) |
C#
// C# program for Number of levels having balanced // parentheses in a Binary Tree using System; using System.Collections; class GFG { // Class containing left and // right child of current // node and key value class Node { public int key; public Node left, right; public Node( int item) { key = item; left = right = null ; } } // Root of Binary Tree static Node root = null ; // Function to count levels in the // Binary Tree having balanced parentheses static int countbal(Node root) { // Stores nodes of each level Queue que = new Queue(); que.Enqueue(root); // Stores required count of // levels with balanced parentheses int ans = 0; // Iterate until false while ( true ) { // Stores parentheses Stack stk = new Stack(); bool flag = true ; int len = que.Count; // If length is false if (len == 0) { break ; } while (len > 0) { // Pop 0 from queue // and store it in temp Node temp = (Node)que.Peek(); que.Dequeue(); // Check if temp.key // is equal to '(' if (temp.key == '(' ) { // push '(' into stack stk.Push( '(' ); } else { // If stk is not empty and the // last element in the stack is '( if (stk.Count > 0 && ( char )stk.Peek() == '(' ) { // Pop from stack stk.Pop(); } else { // Mark flag as False flag = false ; } } // If tmp.left is True if (temp.left != null ) { // push temp.left into queue que.Enqueue(temp.left); } // If tmp.right is True if (temp.right != null ) { // push temp.right into queue que.Enqueue(temp.right); } // Decrement length by 1 len--; } // If flag is True // and stk is False if (flag && stk.Count > 0) { ans += 1; } } return ans; } static void Main() { /*create root*/ // creating all its child root = new Node( '(' ); root.left = new Node( '(' ); root.right = new Node( ')' ); root.left.left = new Node( '(' ); root.left.right = new Node( ')' ); root.right.right = new Node( '(' ); root.left.left.left = new Node( '(' ); root.left.left.right = new Node( '(' ); root.right.right.left = new Node( ')' ); root.right.right.right = new Node( ')' ); // function call and ans print Console.Write(countbal(root)); } } // This code is contributed by decode2207. |
Javascript
<script> // JavaScript program for Number of levels having balanced // parentheses in a Binary Tree class Node { constructor(item) { this .left = null ; this .right = null ; this .key = item; } } // Root of Binary Tree let root; root = null ; // Function to count levels in the // Binary Tree having balanced parentheses function countbal(root) { // Stores nodes of each level let que = []; que.push(root); // Stores required count of // levels with balanced parentheses let ans = 0; // Iterate until false while ( true ) { // Stores parentheses let stk = []; let flag = true ; let len = que.length; // If length is false if (len == 0) { break ; } while (len > 0) { // Pop 0 from queue // and store it in temp let temp = que.shift(); // Check if temp.key // is equal to '(' if (temp.key == '(' ) { // push '(' into stack stk.push( '(' ); } else { // If stk is not empty and the // last element in the stack is '( if (stk.length > 0 && stk[stk.length - 1] == '( ') { // Pop from stack stk.pop(); } else { // Mark flag as False flag = false; } } // If tmp.left is True if (temp.left != null) { // push temp.left into queue que.push(temp.left); } // If tmp.right is True if (temp.right != null) { // push temp.right into queue que.push(temp.right); } // Decrement length by 1 len--; } // If flag is True // and stk is False if (flag && stk.length > 0) { ans += 1; } } return ans; } /*create root*/ // creating all its child root = new Node(' ( '); root.left = new Node(' ( '); root.right = new Node(' ) '); root.left.left = new Node(' ( '); root.left.right = new Node(' ) '); root.right.right = new Node(' ( '); root.left.left.left = new Node(' ( '); root.left.left.right = new Node(' ( '); root.right.right.left = new Node(' ) '); root.right.right.right = new Node(' )'); // function call and ans print document.write(countbal(root)); </script> |
2
Time Complexity: O(N)
Auxiliary Space: O(N)