text: Construct XOR tree by Given leaf nodes of Perfect Binary Tree | C program to build xor tree by leaf nodes of perfect binary tree and root node value of tree ; maximum size for xor tree ; Allocating space to xor tree ; A recursive function that constructs xor tree for array [ start ... . . end ] . x is index of current node in xor tree st ; If there is one element in array , store it in current node of xor tree and return ; printf ( " % d ▁ " , xortree [ x ] ) ; ; for left subtree ; for right subtree ; for getting the middle index from corner indexes . ; Build the left and the right subtrees by xor operation ; merge the left and right subtrees by XOR operation ; Function to construct XOR tree from given array . This function calls construct_Xor_Tree_Util ( ) to fill the allocated memory of xort array ; Driver Code ; leaf nodes of Binary Tree ; Build the xor tree ; Height of xor tree ; Maximum size of xor tree ; Root node is at index 0 considering 0 - based indexing in XOR Tree ; print value at root node
code: #include <math.h> NEW_LINE #include <stdio.h> NEW_LINE #define maxsize  10005 NEW_LINE int xortree [ maxsize ] ; void construct_Xor_Tree_Util ( int current [ ] , int start , int end , int x ) { if ( start == end ) { xortree [ x ] = current [ start ] ; return ; } int left = x * 2 + 1 ; int right = x * 2 + 2 ; int mid = start + ( end - start ) / 2 ; construct_Xor_Tree_Util ( current , start , mid , left ) ; construct_Xor_Tree_Util ( current , mid + 1 , end , right ) ; xortree [ x ] = ( xortree [ left ] ^ xortree [ right ] ) ; } void construct_Xor_Tree ( int arr [ ] , int n ) { int i = 0 ; for ( i = 0 ; i < maxsize ; i ++ ) xortree [ i ] = 0 ; construct_Xor_Tree_Util ( arr , 0 , n - 1 , 0 ) ; } int main ( ) { int leaf_nodes [ ] = { 40 , 32 , 12 , 1 , 4 , 3 , 2 , 7 } , i = 0 ; int n = sizeof ( leaf_nodes ) / sizeof ( leaf_nodes [ 0 ] ) ; construct_Xor_Tree ( leaf_nodes , n ) ; int x = ( int ) ( ceil ( log2 ( n ) ) ) ; int max_size = 2 * ( int ) pow ( 2 , x ) - 1 ; printf ( " Nodes ▁ of ▁ the ▁ XOR ▁ tree STRNEWLINE " ) ; for ( i = 0 ; i < max_size ; i ++ ) { printf ( " % d ▁ " , xortree [ i ] ) ; } int root = 0 ; printf ( " Root : % d " , xortree [ root ] ) ; }