Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Description
2.
Understanding the Input:
3.
Approach
4.
C++ Tree Node Representation
5.
C++ Implementation
6.
Python Tree Node Representation 
7.
Python Implementation
8.
Output:
9.
K-ary Tree Representation
10.
Frequently Asked Questions
10.1.
Explain the full K-ary tree?
10.2.
Explain the preorder traversal of a given tree?
10.3.
Is it possible to construct a Binary Tree using only post-order and preorder traversal?
10.4.
Are the Complete Binary Tree and Full Binary Tree the same?
10.5.
Is it possible to have the pre-order and post-order traversal of a Binary Tree the same?
11.
Conclusion
Last Updated: Mar 27, 2024
Medium

Construct the Full K-ary Tree from its Preorder Traversal

Author Ankit Mishra
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Description

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)

Output:

3 , 6 , 1 , 2 , 1 , 7 , 5 , 2 

K-ary Tree Representation


Check out this problem - Largest BST In Binary Tree

Frequently Asked Questions

Explain the full K-ary tree?

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 TreeBinary Tree Archives.

Recommended problems -

 

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

at the problems, interview experiences and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Previous article
Creating a Binary Tree From Inorder And LevalOrder Traversal
Next article
Find K Smallest Leaf Nodes from a given Binary Tree
Live masterclass