Compress a Binary Tree from top to bottom with overlapping condition | Structure of a node of th tree ; Function to compress all the nodes on the same vertical line ; Stores node by compressing all nodes on the current vertical line ; Check if i - th bit of current bit set or not ; Iterate over the range [ 0 , 31 ] ; Stores count of set bits at i - th positions ; Stores count of clear bits at i - th positions ; Traverse the array ; If i - th bit of current element is set ; Update S ; Update NS ; If count of set bits at i - th position is greater than count of clear bits ; Update ans ; Update getBit ; Function to compress all the nodes on the same vertical line with a single node that satisfies the condition ; Map all the nodes on the same vertical line ; Function to traverse the tree and map all the nodes of same vertical line to vertical distance ; Storing the values in the map ; Recursive calls on left and right subtree ; Getting the range of horizontal distances ; Driver Code ; 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 evalComp ( 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 print ( ans , end = " ▁ " ) NEW_LINE DEDENT def compressTree ( root ) : NEW_LINE INDENT mp = { } NEW_LINE def Trav ( root , hd ) : NEW_LINE INDENT if not root : NEW_LINE INDENT return NEW_LINE DEDENT if hd not in mp : NEW_LINE INDENT mp [ hd ] = [ root . val ] NEW_LINE DEDENT else : NEW_LINE INDENT mp [ hd ] . append ( root . val ) NEW_LINE DEDENT Trav ( root . left , hd - 1 ) NEW_LINE Trav ( root . right , hd + 1 ) NEW_LINE DEDENT Trav ( root , 0 ) NEW_LINE lower = min ( mp . keys ( ) ) NEW_LINE upper = max ( mp . keys ( ) ) NEW_LINE for i in range ( lower , upper + 1 ) : NEW_LINE INDENT evalComp ( mp [ i ] ) NEW_LINE DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT root = TreeNode ( 5 ) NEW_LINE root . left = TreeNode ( 3 ) NEW_LINE root . right = TreeNode ( 2 ) NEW_LINE root . left . left = TreeNode ( 1 ) NEW_LINE root . left . right = TreeNode ( 4 ) NEW_LINE root . right . left = TreeNode ( 1 ) NEW_LINE root . right . right = TreeNode ( 2 ) NEW_LINE compressTree ( root ) NEW_LINE DEDENT