Compress a Binary Tree into an integer diagonally |  ; 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 ; 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 ; Function to compress a given Binary Tree into an integer ; Declare a map ; Store all the compressed values of diagonal elements in an array ; Compress the array into an integer ; Driver Code Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct TreeNode { int val ; TreeNode * left , * right ; TreeNode ( int v ) { val = v ; left = NULL ; right = NULL ; } } ; int findCompressValue ( vector < int > arr ) { int ans = 0 ; int getBit = 1 ; for ( int i = 0 ; i < 32 ; i ++ ) { int S = 0 ; int NS = 0 ; for ( int j : arr ) { if ( getBit & j ) S += 1 ; else NS += 1 ; } if ( S > NS ) ans += pow ( 2 , i ) ; getBit <<= 1 ; } return ans ; } void diagonalOrder ( TreeNode * root , int d , map < int , vector < int > > & mp ) { if ( ! root ) return ; mp [ d ] . push_back ( root -> val ) ; diagonalOrder ( root -> left , d + 1 , mp ) ; diagonalOrder ( root -> right , d , mp ) ; } int findInteger ( TreeNode * root ) { map < int , vector < int > > mp ; diagonalOrder ( root , 0 , mp ) ; vector < int > arr ; for ( auto i : mp ) arr . push_back ( findCompressValue ( i . second ) ) ; return findCompressValue ( arr ) ; } int main ( ) { TreeNode * root = new TreeNode ( 6 ) ; root -> left = new TreeNode ( 5 ) ; root -> right = new TreeNode ( 3 ) ; root -> left -> left = new TreeNode ( 3 ) ; root -> left -> right = new TreeNode ( 5 ) ; root -> right -> left = new TreeNode ( 3 ) ; root -> right -> right = new TreeNode ( 4 ) ; cout << findInteger ( root ) ; return 0 ; }