Untitled

#include <iostream>
#include <vector>

using namespace std;

struct Node
{
  int cost;
  vector<Node *> children;
  Node *parent;
};


void helper(Node *root, int sum_cost, int &ans){
    sum_cost += root->cost;
    if(root->children.size() == 0){
      ans = min(ans, sum_cost);
      return;
    }
    for(int index = 0; index < root->children.size(); index++){
      helper(root->children[index], sum_cost, ans);
    }
}

int getCheapestCost( Node *rootNode )
{
   // your code goes here
  if(!rootNode) return 0;
  int ans = INT_MAX;
  helper(rootNode, 0, ans);
  return ans;
}

int main() {
  Node* root = new Node;
  root->cost = 0;
  root->children.push_back(new Node);
  root->children.push_back(new Node);
  root->children.push_back(new Node);
  root->children[0]->cost = 5;
  root->children[1]->cost = 5;
  root->children[2]->cost = 6;
  cout << getCheapestCost(root) << endl;
  return 0;
}

/*
  Complexity: 
    Time: O(n) // where, n is the total number of nodes.
    Extra Space: O(n)  
    
                              1
                        2           3
                     3      2    3       5 
   
*/