The preorder traversal of the k-ary tree in the sequence is stored and provided in an array arr[]. The aim is to construct the same k-ary tree and output the post-order traversal from it. A full k-ary tree is one in which the root node contains either 0 or k children, i.e., at the most, the child will be k.

Understanding the Input:

The array arr [] has following values {2, 5, 1, 3, 6, 7, 2, 1}

This array(arr) contains the preorder traversal of the K-ary tree.

Now, we have to construct the full k-ary tree and print the post-order traversal of the constructed tree. In simple words, a full k-ary tree is a tree where each node has either 0 or k numbers of children.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Approach

We'll start by making a k-ary tree out of the given array, with the first element working as the root node. If the left subtree is empty, the right subtree will also be empty. Recursively look for and connect the left and right subtrees. For the post-order traversal, we use the left subtree and right subtree and finally output the node's weight.

The first root node is analyzed in preorder traversal, followed by the left and right subtree. As a result, to build a complete k-ary tree, we just need to keep constructing nodes without regard for the previously produced nodes. This can be used to build the tree recursively.

The steps to solving the problem are as follows:

1. Determine the tree's height.

2. Iterate through the preorder array, recursively adding each node.

C++ Tree Node Representation

struct TreeNode
{
int data;
vector<TreeNode *> child;
};

C++ Implementation

#include <bits/stdc++.h>
using namespace std;
// Only a Helper/Utility function
// node with temp children
TreeNode *newNode(int value)
{
TreeNode *nNode = new TreeNode;
nNode->data = value;
return nNode;
}
// Function to build full temp-ary tree
TreeNode *Build_K_ary_Tree(int A[], int size, int temp, int h, int &index_i)
{
// Base Case
if (size <= 0)
return NULL;
TreeNode *nNode = newNode(A[index_i]);
if (nNode == NULL)
{
cout << "Memory error" << endl;
return NULL;
}
// For adding temp children to a node
for (int i = 0; i < temp; i++)
{
// Checking for index_i is in range of array
// Checking for height of the tree is greater than 1
if (index_i < size - 1 && h > 1)
{
index_i++;
// Recursively adding each child to the Tree
nNode->child.push_back(Build_K_ary_Tree(A, size, temp, h - 1, index_i));
}
else
{
nNode->child.push_back(NULL);
}
}
return nNode;
}
// Returns the height of the tree
TreeNode *Build_K_ary_Tree(int *A, int size, int temp, int index_i)
{
int height = (int)ceil(log((double)size * (temp - 1) + 1) / log((double)temp));
return Build_K_ary_Tree(A, size, temp, height, index_i);
}
// Printing postorder traversal of the tree
void Traversal_postorder(TreeNode *root, int temp)
{
if (root == NULL)
return;
for (int i = 0; i < temp; i++)
Traversal_postorder(root->child[i], temp);
cout << root->data << " ";
}
// Main Function
//temp-> number of children
int main()
{
int index_i = 0;
int temp = 2, size = 8;
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1};
TreeNode *root = Build_K_ary_Tree(arr, size, temp, index_i);
Traversal_postorder(root, temp);
cout << endl;
return 0;
}

Python Tree Node Representation

# Utility function
class TreeNode:
def __init__(self, value):
self.key = value
self.child = []

Python Implementation

from math import ceil, log@# building full temp-ary tree@def BuildkaryTree(A, size, temp, h, index):@ @ # Base Case@ if (size <= 0):@ return None@@ nNode = TreeNode(A[index[0]])@ if (nNode == None):@ print("Memory error")@ return None@ for i in range(temp):@ # Check if the index is in the range of array@ # Check if the height of the tree is@ # greater than 1@ if (index[0] < size - 1 and h > 1):@ index[0] += 1@@ # Recursively add each child@ nNode.child.append(BuildkaryTree(A, size, temp,@ h - 1, index))@ else:@ nNode.child.append(None)@ return nNode@@#Finding height of the tree@def Build_K_ary_Tree(A, size, temp, index):@ height = int(ceil(log(float(size) * (temp - 1) + 1) /@ log(float(temp))))@ return BuildkaryTree(A, size, temp, height, index)@@# printing postorder traversal@def traversal_post_order(root, temp):@ if (root == None):@ return@ for i in range(temp):@ traversal_post_order(root.child[i], temp)@ print(root.key, end = " ")@@# Driver Code@if __name__ == '__main__':@ index = [0]@ temp = 2@ size = 8@ arr = [ 2, 5, 1, 3, 6, 7, 2, 1]@ root = Build_K_ary_Tree(arr, size, temp, index)@ traversal_post_order(root, temp)

The K-ary tree is a rooted tree with a maximum of k children in each node. This is known as a binary tree if the value of k is 2. Binary trees, often known as ternary trees, are specialized k-ary trees.

Explain the preorder traversal of a given tree?

To make a clone of the tree, preorder traversal is required. On an expression tree, preorder traversal is also utilized to get prefix expression.

Is it possible to construct a Binary Tree using only post-order and preorder traversal?

In some cases, it is possible to construct the Full Binary tree.

Are the Complete Binary Tree and Full Binary Tree the same?

A full binary tree ( which is also known as a correct binary tree or 2-tree) is a tree in which every node has two offspring save the leaves. A complete binary tree is one in which every level is completely filled, save potentially the last, and all nodes are as far left as feasible.

Is it possible to have the pre-order and post-order traversal of a Binary Tree the same?

The answer is a NO. This is how an ordered tree with more than one node (for example, two nodes) looks. Pre-order traversal visits nodes in the order root-left-right, while post-order traversal visits nodes in the order root-left-right.

Conclusion

In this article, we have extensively discussed the Binary Tree Question, which is rated between Medium to Hard Level, and discussed the approach for the Problem and implementation of the approach in the most straightforward manner.

After reading about the question, are you not feeling excited to read/explore more articles on the topic of Trees? Don't worry; Coding Ninjas has you covered. To learn, see Binary Tree, Binary Tree Archives.

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses, refer to the mock test and problems; look at the interview experiences and interview bundle for placement preparations. Check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look