Reuse intermediate values in N-ary tree compute expression

reuse_intermediate_compute_tree.cpp

/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <iostream>
#include <vector>
#include <queue>
#include <memory>
#include <unordered_map>

using namespace std;

struct Node {
    int val;
    vector<unique_ptr<Node, void(*)(Node*)>> children; // children node with custom deleter
    Node(int value) : val(value) {}
};

// Lambda for custom deleter
auto deleter = [](Node* node) {
    if (node) {
        for(auto& child : node->children) {
            child.reset(); // Explicitely delete child node
        }
        delete node;
    }
};


void computeProductsWithMap(const Node* node, int currentProduct,
    unordered_map<const Node*, int>& productMap) {
        
    if (!node) return;
    
    currentProduct *= node->val;
    productMap[node] = currentProduct;
    
    for (const auto& child : node->children) {
        computeProductsWithMap(child.get(), currentProduct, productMap);
    }
    
}

unique_ptr<Node, void(*)(Node*)> createTree() {
    // Create the root node
    auto root = unique_ptr<Node, decltype(deleter)>(new Node(1), deleter);

    // Level 1 children
    auto child1 = unique_ptr<Node, decltype(deleter)>(new Node(2), deleter);
    auto child2 = unique_ptr<Node, decltype(deleter)>(new Node(3), deleter);

    // Level 2 children for child1
    auto child1_1 = unique_ptr<Node, decltype(deleter)>(new Node(4), deleter);
    auto child1_2 = unique_ptr<Node, decltype(deleter)>(new Node(5), deleter);

    // Level 2 children for child2
    auto child2_1 = unique_ptr<Node, decltype(deleter)>(new Node(6), deleter);

    // Level 3 children for child1_1
    child1_1->children.push_back(unique_ptr<Node, decltype(deleter)>(new Node(7), deleter));
    child1_1->children.push_back(unique_ptr<Node, decltype(deleter)>(new Node(8), deleter));

    // Level 4 child for child1_1's first child
    child1_1->children[0]->children.push_back(unique_ptr<Node, decltype(deleter)>(new Node(9), deleter));

    // Level 5 child for the deeper path
    child1_1->children[0]->children[0]->children.push_back(unique_ptr<Node, decltype(deleter)>(new Node(10), deleter));

    // Attach children to child1
    child1->children.push_back(move(child1_1));
    child1->children.push_back(move(child1_2));

    // Attach children to child2
    child2->children.push_back(move(child2_1));

    // Attach children to root
    root->children.push_back(move(child1));
    root->children.push_back(move(child2));
    
    return root;
}

void preorder(const Node* root) {
    if (!root) return;
    
    cout << root->val << " ";
    
    for (const auto& child : root->children) {
        preorder(child.get());
    }
}

int main()
{
    std::cout<<"Hello World\n";

    auto tree = createTree();
    unordered_map<const Node*, int> productMap;
    computeProductsWithMap(tree.get(), 1, productMap);

    for (const auto& [node, product] : productMap) {
        cout << "Node value: " << node->val << ", Product: " << product << endl;
    }

    preorder(tree.get());
    return 0;
}