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 { constructor ( val = " " , left = null , right = null ) { this . val = val ; this . left = left ; this . right = right ; } } function evalComp ( arr ) { let ans = 0 ; let getBit = 1 ; for ( let i = 0 ; i < 32 ; i ++ ) { let S = 0 ; let NS = 0 ; for ( j of arr ) { if ( getBit & j ) S += 1 ; else NS += 1 ; } if ( S > NS ) ans += 2 ** i ; getBit <<= 1 ; } document . write ( ans + " " ) ; } function compressTree ( root ) { let mp = new Map ( ) ; function Trav ( root , hd ) { if ( ! root ) return ; if ( ! mp . has ( hd ) ) mp . set ( hd , [ root . val ] ) ; else { let temp = mp . get ( hd ) ; temp . push ( root . val ) ; mp . set ( hd , temp ) ; } Trav ( root . left , hd - 1 ) ; Trav ( root . right , hd + 1 ) ; } Trav ( root , 0 ) ; let lower = [ ... mp . keys ( ) ] . sort ( ( a , b ) => a - b ) [ 0 ] ; let upper = [ ... mp . keys ( ) ] . sort ( ( a , b ) => b - a ) [ 0 ] ; for ( let i = lower ; i <= upper ; i ++ ) evalComp ( mp . get ( i ) ) ; } let root = new TreeNode ( 5 ) ; root . left = new TreeNode ( 3 ) ; root . right = new TreeNode ( 2 ) ; root . left . left = new TreeNode ( 1 ) ; root . left . right = new TreeNode ( 4 ) ; root . right . left = new TreeNode ( 1 ) ; root . right . right = new TreeNode ( 2 ) ; compressTree ( root ) ;