Construct the full k | Python3 program to build full k - ary tree from its preorder traversal and to print the postorder traversal of the tree . ; Utility function to create a new tree node with k children ; Function to build full k - ary tree ; For None tree ; For adding k children to a node ; Check if ind is in range of array Check if height of the tree is greater than 1 ; Recursively add each child ; Function to find the height of the tree ; Function to prpostorder traversal of the tree ; Driver Code
from math import ceil , log NEW_LINE class newNode : NEW_LINE INDENT def __init__ ( self , value ) : NEW_LINE INDENT self . key = value NEW_LINE self . child = [ ] NEW_LINE DEDENT DEDENT def BuildkaryTree ( A , n , k , h , ind ) : NEW_LINE INDENT if ( n <= 0 ) : NEW_LINE INDENT return None NEW_LINE DEDENT nNode = newNode ( A [ ind [ 0 ] ] ) NEW_LINE if ( nNode == None ) : NEW_LINE INDENT print ( " Memory ▁ error " ) NEW_LINE return None NEW_LINE DEDENT for i in range ( k ) : NEW_LINE INDENT if ( ind [ 0 ] < n - 1 and h > 1 ) : NEW_LINE INDENT ind [ 0 ] += 1 NEW_LINE nNode . child . append ( BuildkaryTree ( A , n , k , h - 1 , ind ) ) NEW_LINE DEDENT else : NEW_LINE INDENT nNode . child . append ( None ) NEW_LINE DEDENT DEDENT return nNode NEW_LINE DEDENT def BuildKaryTree ( A , n , k , ind ) : NEW_LINE INDENT height = int ( ceil ( log ( float ( n ) * ( k - 1 ) + 1 ) / log ( float ( k ) ) ) ) NEW_LINE return BuildkaryTree ( A , n , k , height , ind ) NEW_LINE DEDENT def postord ( root , k ) : NEW_LINE INDENT if ( root == None ) : NEW_LINE INDENT return NEW_LINE DEDENT for i in range ( k ) : NEW_LINE INDENT postord ( root . child [ i ] , k ) NEW_LINE DEDENT print ( root . key , end = " ▁ " ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT ind = [ 0 ] NEW_LINE k = 3 NEW_LINE n = 10 NEW_LINE preorder = [ 1 , 2 , 5 , 6 , 7 , 3 , 8 , 9 , 10 , 4 ] NEW_LINE root = BuildKaryTree ( preorder , n , k , ind ) NEW_LINE print ( " Postorder ▁ traversal ▁ of ▁ constructed " , " full ▁ k - ary ▁ tree ▁ is : ▁ " ) NEW_LINE postord ( root , k ) NEW_LINE DEDENT