Count levels in a Binary Tree consisting of node values having set bits at different positions | 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
class TreeNode : NEW_LINE INDENT def __init__ ( self , val = 0 , left = None , right = None ) : NEW_LINE INDENT self . val = val NEW_LINE self . left = left NEW_LINE self . right = right NEW_LINE DEDENT DEDENT def uniqueLevels ( root ) : NEW_LINE INDENT uniqueLevels = 0 NEW_LINE que = [ root ] NEW_LINE while len ( que ) : NEW_LINE INDENT length = len ( que ) NEW_LINE prefix_XOR = 0 ; NEW_LINE prefix_OR = 0 NEW_LINE flag = True NEW_LINE while length : NEW_LINE INDENT temp = que . pop ( 0 ) NEW_LINE prefix_OR |= temp . val NEW_LINE prefix_XOR ^= temp . val NEW_LINE if prefix_XOR != prefix_OR : NEW_LINE INDENT flag = False NEW_LINE DEDENT if temp . left : NEW_LINE INDENT que . append ( temp . left ) NEW_LINE DEDENT if temp . right : NEW_LINE INDENT que . append ( temp . right ) NEW_LINE DEDENT length -= 1 NEW_LINE DEDENT if flag : NEW_LINE INDENT uniqueLevels += 1 NEW_LINE DEDENT DEDENT print ( uniqueLevels ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = TreeNode ( 5 ) NEW_LINE root . left = TreeNode ( 6 ) NEW_LINE root . right = TreeNode ( 9 ) NEW_LINE root . left . left = TreeNode ( 1 ) NEW_LINE root . left . right = TreeNode ( 4 ) NEW_LINE root . right . right = TreeNode ( 7 ) NEW_LINE uniqueLevels ( root ) NEW_LINE DEDENT