Construct XOR tree by Given leaf nodes of Perfect Binary Tree | Python3 implementation of the above approach ; Maximum size for xor tree ; Allocating space to xor tree ; A recursive function that constructs xor tree for vector array [ start ... . . end ] . x is index of current node in XOR tree ; If there is one element in vector array , store it in current node of XOR tree ; cout << xor_tree [ x ] << " ▁ 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 the given vector array . This function calls construct_Xor_Tree_Util ( ) to fill the allocated memory of xor_tree vector array ; Driver Code ; leaf nodes of Perfect 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 ; prevalue at root node
from math import ceil , log NEW_LINE maxsize = 100005 NEW_LINE xor_tree = [ 0 ] * maxsize NEW_LINE def construct_Xor_Tree_Util ( current , start , end , x ) : NEW_LINE INDENT if ( start == end ) : NEW_LINE INDENT xor_tree [ x ] = current [ start ] NEW_LINE return NEW_LINE DEDENT left = x * 2 + 1 NEW_LINE right = x * 2 + 2 NEW_LINE mid = start + ( end - start ) // 2 NEW_LINE construct_Xor_Tree_Util ( current , start , mid , left ) NEW_LINE construct_Xor_Tree_Util ( current , mid + 1 , end , right ) NEW_LINE xor_tree [ x ] = ( xor_tree [ left ] ^ xor_tree [ right ] ) NEW_LINE DEDENT def construct_Xor_Tree ( arr , n ) : NEW_LINE INDENT construct_Xor_Tree_Util ( arr , 0 , n - 1 , 0 ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT leaf_nodes = [ 40 , 32 , 12 , 1 , 4 , 3 , 2 , 7 ] NEW_LINE n = len ( leaf_nodes ) NEW_LINE construct_Xor_Tree ( leaf_nodes , n ) NEW_LINE x = ( ceil ( log ( n , 2 ) ) ) NEW_LINE max_size = 2 * pow ( 2 , x ) - 1 NEW_LINE print ( " Nodes ▁ of ▁ the ▁ XOR ▁ Tree : " ) NEW_LINE for i in range ( max_size ) : NEW_LINE INDENT print ( xor_tree [ i ] , end = " ▁ " ) NEW_LINE DEDENT root = 0 NEW_LINE print ( " Root :   " , xor_tree [ root ] ) NEW_LINE DEDENT