#include <bits/stdc++.h>
using namespace std;
template <typename T> class Node {
public:
Node(T data);
Node* get_first_child() const;
Node* get_next_sibling() const;
void set_next_sibling(Node* node);
void set_next_child(Node* node);
T get_data();
private:
T data;
Node* first_child;
Node* next_sibling;
};
template <typename T> Node<T>::Node(T data)
{
first_child = NULL;
next_sibling = NULL;
this->data = data;
}
template <typename T>
Node<T>* Node<T>::get_first_child() const
{
return first_child;
}
template <typename T>
Node<T>* Node<T>::get_next_sibling() const
{
return next_sibling;
}
template <typename T>
void Node<T>::set_next_sibling(Node<T>* node)
{
if (next_sibling == NULL) {
next_sibling = node;
}
else {
next_sibling->set_next_sibling(node);
}
}
template <typename T> T Node<T>::get_data() { return data; }
template <typename T>
void Node<T>::set_next_child(Node<T>* node)
{
if (first_child == NULL) {
first_child = node;
}
else {
first_child->set_next_sibling(node);
}
}
template <typename T>
Node<T>* Construct(T* post_order_arr, int size, int k)
{
Node<T>* Root = new Node<T>(post_order_arr[size - 1]);
if (size == 1) {
return Root;
}
int height_of_tree
= ceil(log2(size * (k - 1) + 1) / log2(k)) - 1;
int nodes_in_last_level
= size - ((pow(k, height_of_tree) - 1) / (k - 1));
int tracker = 0;
while (tracker != (size - 1)) {
int last_level_nodes
= (pow(k, height_of_tree - 1)
> nodes_in_last_level)
? nodes_in_last_level
: (pow(k, height_of_tree - 1));
int nodes_in_next_subtree
= ((pow(k, height_of_tree - 1) - 1) / (k - 1))
+ last_level_nodes;
Root->set_next_child(
Construct(post_order_arr + tracker,
nodes_in_next_subtree, k));
tracker = tracker + nodes_in_next_subtree;
nodes_in_last_level
= nodes_in_last_level - last_level_nodes;
}
return Root;
}
template <typename T> void preorder(Node<T>* Root)
{
if (Root == NULL) {
return;
}
cout << Root->get_data() << " ";
preorder(Root->get_first_child());
preorder(Root->get_next_sibling());
}
int main()
{
int M = 9, N = 3;
int arr[] = { 5, 6, 7, 2, 8, 9, 3, 4, 1 };
preorder(Construct(arr, M, N));
return 0;
}
