Compress a Binary Tree into an integer diagonally | Python program for the above approach ; Function to compress the elements in an array into an integer ; Check for each bit position ; Update the count of set and non - set bits ; If number of set bits exceeds the number of non - set bits , then add set bits value to ans ; Function to compress a given Binary Tree into an integer ; Declare a map ; Perform Inorder Traversal on the Binary Tree ; Store all nodes of the same line together as a vector ; Increase the vertical distance of left child ; Vertical distance remains same for right child ; Store all the compressed values of diagonal elements in an array ; Compress the array into an integer ; Driver Code Given Input ; Function Call
class TreeNode : NEW_LINE INDENT def __init__ ( self , val = ' ' , 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 findCompressValue ( arr ) : NEW_LINE INDENT ans = 0 NEW_LINE getBit = 1 NEW_LINE for i in range ( 32 ) : NEW_LINE INDENT S = 0 NEW_LINE NS = 0 NEW_LINE for j in arr : NEW_LINE INDENT if getBit & j : NEW_LINE INDENT S += 1 NEW_LINE DEDENT else : NEW_LINE INDENT NS += 1 NEW_LINE DEDENT DEDENT if S > NS : NEW_LINE INDENT ans += 2 ** i NEW_LINE DEDENT getBit <<= 1 NEW_LINE DEDENT return ans NEW_LINE DEDENT def findInteger ( root ) : NEW_LINE INDENT mp = { } NEW_LINE def diagonalOrder ( root , d , mp ) : NEW_LINE INDENT if not root : NEW_LINE INDENT return NEW_LINE DEDENT try : NEW_LINE INDENT mp [ d ] . append ( root . val ) NEW_LINE DEDENT except KeyError : NEW_LINE INDENT mp [ d ] = [ root . val ] NEW_LINE DEDENT diagonalOrder ( root . left , d + 1 , mp ) NEW_LINE diagonalOrder ( root . right , d , mp ) NEW_LINE DEDENT diagonalOrder ( root , 0 , mp ) NEW_LINE arr = [ ] NEW_LINE for i in mp : NEW_LINE INDENT arr . append ( findCompressValue ( mp [ i ] ) ) NEW_LINE DEDENT return findCompressValue ( arr ) NEW_LINE DEDENT root = TreeNode ( 6 ) NEW_LINE root . left = TreeNode ( 5 ) NEW_LINE root . right = TreeNode ( 3 ) NEW_LINE root . left . left = TreeNode ( 3 ) NEW_LINE root . left . right = TreeNode ( 5 ) NEW_LINE root . right . left = TreeNode ( 3 ) NEW_LINE root . right . right = TreeNode ( 4 ) NEW_LINE print ( findInteger ( root ) ) NEW_LINE