CODEWITHSUNDEEP
c++algorithmtree
user521968
user521968

Reputation:

Finding the path of the minimum in a tree

This is a problem in my research code and I am wondering what is the efficient way to go about doing this. I am leaving out unnecessary details and I am presenting it in a manner so that the crux of the problem can be understood.

Lets say I have a binary tree with numbers on each node. I want to find the minimum sum of all the branches in the tree starting from root to leaf. Below is a very rough pseudocode.

int minimum(tree){
   // Some base cases
   left_min = minimum(tree->left);
   right_min= minimum(tree->right);
   if (left_min < right_min){
      return current_value + left_min;
   }
   else{
      return current_value + right_min;
   }
}

From this, I can compute the minimum. However, if I want to compute the nodes which give me the minimum, how would I go about? i.e. if the answer is say 14, I want to find out which nodes at each level in the tree add up to give me a sum of 14. What would be the efficient way to go about doing this with minimal change to the existing function? By minimal change, I mean I can add additional variables to keep track of the branch but not rewrite the function completely.

Thanks

Upvotes: 3

Views: 253

Answers (2)

perreal
perreal

Reputation: 97968

You can use a list/queue as an extra argument to keep track of selected nodes:

int minimum(tree, list){
   List templeft, tempright;
   // Some base cases
   left_min = minimum(tree->left, templeft);
   right_min= minimum(tree->right, tempright);
   if (left_min < right_min){
      list.push_back(templeft);
      list.push_back(current);
      return current_value + left_min;
   }
   else{
      list.push_back(tempright);
      list.push_back(current);
      return current_value + right_min;
   }
}

Upvotes: 2

walrii
walrii

Reputation: 3522

You can use a list or stack or queue instead of vector:

typedef vector<yourIdType> idvec;

int minimum(tree, idvec &path){
   // Some base cases
   idvec leftPath, rightPath;
   left_min = minimum(tree->left, leftPath);
   right_min= minimum(tree->right, rightPath);
   if (left_min < right_min){
      swap(path, leftPath);
      path.push_back(thisNodeId);
      return current_value + left_min;
   } else {
      swap(path, rightPath);
      path.push_back(thisNodeId);
      return current_value + right_min;
   }
}

Upvotes: 3

Related Questions