Select Page

Construct a Complete N-ary Tree from given Postorder Traversal

Animesh Dey
Published: June 3, 2022

  

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

}

Source: www.geeksforgeeks.org