Construct the Full K-ary Tree from its Preorder Traversal

C++ Tree Node Representation

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

You can also try this code with Online C++ Compiler

Run Code

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;
}

You can also try this code with Online C++ Compiler

Run Code

Python Tree Node Representation 

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

You can also try this code with Online Python Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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 Tree, Binary Tree Archives.

Recommended problems -

• Preorder Traversal
• Zig Zag Tree Traversal 

Refer to our guided paths on Code360 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! 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.