Member Avatar for xtinab

Hello all,

I'm having trouble writing a recursive algorithm to traverse a Huffman tree to encode a message. I'm sure you all know what they are.

Here's my algorithm:

string HuffmanCode(const char& symbol, const TreeNode<SymbolPriority>* huffman, string &code)
{
    //Base case: you are in a leaf; if the leaf contains the character 
    //you are looking for then return the code (third argument) 
    //else return an empty string (which means ‘wrong leaf’).
    if(huffman->IsLeaf())
    {
        if(huffman->Value.Symbol == symbol)
            return code;
        else
            return "";
    }

    /*always start by going to the left and adding ‘0’ to the code 
    (code + ‘0’); check the return value against the empty string: 
    if the return value is not empty then return it without going 
    to the right else return the result of going to the right 
    (do not forget to add ‘1’ to the code).*/

    else
    {
        HuffmanCode(symbol, huffman->Left, code+'0');
        HuffmanCode(symbol, huffman->Right, code+'1');
    }
}

The problem is that when I traverse the tree and it exits when it sees that the symbol in the leaf doesn't match the symbol being looked for, it exits and goes into the right tree. Even if it finds it, it'll return and go back into the left sub tree.

Any help will be appreciated!

  • 2 Contributors
  • 1 Reply
  • 1K Views
  • 3 Hours Discussion Span
  • Latest Post Latest Post by histrungalot

Dani AI

Generated

The bug is not the tree: it’s how the recursive calls and the code parameter are being used. Two concrete issues to fix:

  • The result of a recursive call must be returned (or otherwise propagated). If you call the left subtree but ignore its return value, a found code will be lost.
  • In C++ you cannot bind a temporary like code + '0' to a non-const string&. Either pass the path by value (return it) or mutate a string& with push/pop as you descend.

A robust, efficient pattern is backtracking: mutate a single string while descending and pop the last char when you return. That avoids allocating new strings on every call and makes it easy to return a boolean success flag:

bool findCode(char symbol, const TreeNode<SymbolPriority>* node, std::string &out) {
    if (!node) return false;
    if (node->IsLeaf()) return node->Value.Symbol == symbol;
    out.push_back('0');
    if (findCode(symbol, node->Left, out)) return true;
    out.pop_back();
    out.push_back('1');
    if (findCode(symbol, node->Right, out)) return true;
    out.pop_back();
    return false;
}

// usage:
std::string code;
if (findCode(targetChar, root, code)) { /* code contains encoding */ }

For encoding whole messages, do one traversal to build a map from symbol→code (backtracking again) and then encode in O(message_length). ’s suggestion to check and return the left result is on the right track; the backtracking approach above is both simpler to reason about and more efficient for repeated lookups.

Member Avatar for histrungalot

This works in my head, can't check it unless I code it up or some simple binary tree. At the end the value return by HuffmanCode will have the encoded value not code (third arg).

int main() {
   // etc...

   someChar  = 'n';
   wrkingTmp = "";  // <--- Will not hold the result
   encoding = HuffmanCode(someChar, root, wrkingTmp);
   cout << "Encoding for " << someChar << " is " << encoding << endl;

   // etc...
}

string HuffmanCode(const char& symbol, const TreeNode<SymbolPriority>* huffman, string &code)
{
    // Init the return value
    string ret("");
    if(huffman->IsLeaf()){
        if(huffman->Value.Symbol == symbol){
            // Set the return to the encoded value
            ret = code;
        }
    }
    else
    {
      // Go to the left, if empty string is returned, go to the right
      if ( (ret = HuffmanCode(symbol, huffman->Left, code+'0')) == "" ){
         // Go to the right
         ret = HuffmanCode(symbol, huffman->Right, code+'1'); 
      }
    }
    // Always return something
    return ret;
}
Edited by histrungalot because: Fixing
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.