# Construct the full k-ary tree from its preorder traversal

Given an array which contains the preorder traversal of full k-ary tree, construct the full k-ary tree and print its postorder traversal. A full k-ary tree is a tree where each node has either 0 or k children.

Examples:

```Input : preorder[] = {1, 2, 5, 6, 7,
3, 8, 9, 10, 4}
k = 3
Output : Postorder traversal of constructed
full k-ary tree is: 5 6 7 2 8 9 10
3 4 1
Tree formed is:         1
/   |
2     3    4
/|   /|
5 6 7 8 9 10

Input : preorder[] = {1, 2, 5, 6, 7, 3, 4}
k = 3
Output : Postorder traversal of constructed
full k-ary tree is: 5 6 7 2 3 4 1
Tree formed is:        1
/  |
2    3   4
/|
5 6 7
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We have discussed this problem for Binary tree in below post.
Construct a special tree from given preorder traversal
In this post, solution for a k-ary tree is discussed.

In Preorder traversal, first root node is processed then followed by the left subtree and right subtree. Because of this, to construct a full k-ary tree, we just need to keep on creating the nodes without bothering about the previous constructed nodes. We can use this to build the tree recursively.
Following are the steps to solve the problem:
1. Find the height of the tree.
2. Traverse the preorder array and recursively add each node

## C++

 `// C++ program to build full k-ary tree from ` `// its preorder traversal and to print the ` `// postorder traversal of the tree. ` `#include ` `using` `namespace` `std; ` ` `  `// Structure of a node of an n-ary tree ` `struct` `Node { ` `    ``int` `key; ` `    ``vector child; ` `}; ` ` `  `// Utility function to create a new tree  ` `// node with k children ` `Node* newNode(``int` `value) ` `{ ` `    ``Node* nNode = ``new` `Node; ` `    ``nNode->key = value; ` `    ``return` `nNode; ` `} ` ` `  `// Function to build full k-ary tree ` `Node* BuildKaryTree(``int` `A[], ``int` `n, ``int` `k, ``int` `h, ``int``& ind) ` `{ ` `    ``// For null tree ` `    ``if` `(n <= 0) ` `        ``return` `NULL; ` ` `  `    ``Node* nNode = newNode(A[ind]); ` `    ``if` `(nNode == NULL) { ` `        ``cout << ``"Memory error"` `<< endl; ` `        ``return` `NULL; ` `    ``} ` ` `  `    ``// For adding k children to a node ` `    ``for` `(``int` `i = 0; i < k; i++) { ` ` `  `        ``// Check if ind is in range of array ` `        ``// Check if height of the tree is greater than 1 ` `        ``if` `(ind < n - 1 && h > 1) { ` `            ``ind++; ` ` `  `            ``// Recursively add each child ` `            ``nNode->child.push_back(BuildKaryTree(A, n, k, h - 1, ind)); ` `        ``} ``else` `{ ` `            ``nNode->child.push_back(NULL); ` `        ``} ` `    ``} ` `    ``return` `nNode; ` `} ` ` `  `// Function to find the height of the tree ` `Node* BuildKaryTree(``int``* A, ``int` `n, ``int` `k, ``int` `ind) ` `{ ` `    ``int` `height = (``int``)``ceil``(``log``((``double``)n * (k - 1) + 1)  ` `                 ``/ ``log``((``double``)k)); ` `    ``return` `BuildKaryTree(A, n, k, height, ind); ` `} ` ` `  `// Function to print postorder traversal of the tree ` `void` `postord(Node* root, ``int` `k) ` `{ ` `    ``if` `(root == NULL) ` `        ``return``; ` `    ``for` `(``int` `i = 0; i < k; i++) ` `        ``postord(root->child[i], k); ` `    ``cout << root->key << ``" "``; ` `} ` ` `  `// Driver program to implement full k-ary tree ` `int` `main() ` `{ ` `    ``int` `ind = 0; ` `    ``int` `k = 3, n = 10; ` `    ``int` `preorder[] = { 1, 2, 5, 6, 7, 3, 8, 9, 10, 4 }; ` `    ``Node* root = BuildKaryTree(preorder, n, k, ind); ` `    ``cout << ``"Postorder traversal of constructed"` `             ``" full k-ary tree is: "``; ` `    ``postord(root, k); ` `    ``cout << endl; ` `    ``return` `0; ` `} `

## Python3

# Python3 program to build full k-ary tree
# from its preorder traversal and to prthe
# postorder traversal of the tree.
from math import ceil, log

# Utility function to create a new
# tree node with k children
class newNode:
def __init__(self, value):
self.key = value
self.child = []

# Function to build full k-ary tree
def BuildkaryTree(A, n, k, h, ind):

# For None tree
if (n <= 0): return None nNode = newNode(A[ind[0]]) if (nNode == None): print("Memory error") return None # For adding k children to a node for i in range(k): # Check if ind is in range of array # Check if height of the tree is # greater than 1 if (ind[0] < n - 1 and h > 1):
ind[0] += 1

nNode.child.append(BuildkaryTree(A, n, k,
h – 1, ind))
else:
nNode.child.append(None)
return nNode

# Function to find the height of the tree
def BuildKaryTree(A, n, k, ind):
height = int(ceil(log(float(n) * (k – 1) + 1) /
log(float(k))))
return BuildkaryTree(A, n, k, height, ind)

# Function to prpostorder traversal
# of the tree
def postord(root, k):
if (root == None):
return
for i in range(k):
postord(root.child[i], k)
print(root.key, end = ” “)

# Driver Code
if __name__ == ‘__main__’:
ind = [0]
k = 3
n = 10
preorder = [ 1, 2, 5, 6, 7, 3, 8, 9, 10, 4]
root = BuildKaryTree(preorder, n, k, ind)
print(“Postorder traversal of constructed”,
“full k-ary tree is: “)
postord(root, k)

# This code is contributed by pranchalK

Output:

```Postorder traversal of constructed full k-ary
tree is: 5 6 7 2 8 9 10 3 4 1
```

## tags:

Tree n-ary-tree Tree