Count levels in a Binary Tree consisting of node values having set bits at different positions | C ++ program for the above approach ; Structure of a node in the binary tree ; Function to find total unique levels ; Stores count of levels , where the set bits of all the nodes are at different positions ; Store nodes at each level of the tree using BFS ; Performing level order traversal ; Stores count of nodes at current level ; Stores prefix XOR of all the nodes at current level ; Stores prefix OR of all the nodes at current level ; Check if set bit of all the nodes at current level is at different positions or not ; Traverse nodes at current level ; Stores front element of the que ; Update prefix_OR ; Update prefix_XOR ; If left subtree not NULL ; If right subtree not NULL ; If bitwise AND is zero ; Driver Code ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct TreeNode { int val = 0 ; TreeNode * left , * right ; TreeNode ( int x ) { val = x ; left = NULL ; right = NULL ; } } ; void uniqueLevels ( TreeNode * root ) { int uniqueLevels = 0 ; queue < TreeNode * > que ; que . push ( root ) ; while ( que . size ( ) > 0 ) { int length = que . size ( ) ; int prefix_XOR = 0 ; int prefix_OR = 0 ; bool flag = true ; for ( int i = 0 ; i < length ; i ++ ) { TreeNode * temp = que . front ( ) ; que . pop ( ) ; prefix_OR |= temp -> val ; prefix_XOR ^= temp -> val ; if ( prefix_XOR != prefix_OR ) flag = false ; if ( temp -> left ) que . push ( temp -> left ) ; if ( temp -> right ) que . push ( temp -> right ) ; } if ( flag ) uniqueLevels += 1 ; } cout << uniqueLevels ; } int main ( ) { TreeNode * root = new TreeNode ( 5 ) ; root -> left = new TreeNode ( 6 ) ; root -> right = new TreeNode ( 9 ) ; root -> left -> left = new TreeNode ( 1 ) ; root -> left -> right = new TreeNode ( 4 ) ; root -> right -> right = new TreeNode ( 7 ) ; uniqueLevels ( root ) ; return 0 ; }