Tree: Huffman Decoding

Sort by

recency

|

83 Discussions

|

  • + 0 comments

    much simpler than I was anticipating :D

    C++14 solution:

    void decode_huff(node * root, string s) {
        string result;
        node* ptr = root;
        for (int i = 0; i < s.size(); ++i) {
            switch (s[i]) {
                case '0': ptr = ptr->left; break;
                case '1': ptr = ptr->right; break;
            }
            if (!ptr->left && !ptr->right) {
                result += ptr->data;
                ptr = root;
            }
        }
        cout << result << endl;
    }
    
  • + 1 comment

    Unfortunately, this question does not currently work in JavaScript.

    Python and C++14 (among others) are given decodeHuff(root, s) as the function to modify and are given the Node class and its constructors, while JavaScript just gives you a meaningless processData(input) function.

    I worked with it, confused, for about 15 minutes before I tried it in another browser, then came to the Discussion posts here and realized the question was glitched.

    Please give us JavaScript users decodeHuff(root, s) as well. :) Would love to solve this problem as part of my interview prep. Thanks.

  • + 0 comments

    Yet another bunk question in the interview prep...

    This was my working solution lol:

    function processData(input) { console.log(input) }

  • + 0 comments
    void iter(node * root, std::string key, std::map<std::string, std::string> &dictionary){
    
    if(root == NULL){
        return;
    }
    
    if(root->data != '\0') {
        std::string s{root->data};
        dictionary[key] = s;
    }
    
    iter(root->left, key+"0", dictionary);
    iter(root->right, key+"1", dictionary);
    }
    
    void decode_huff(node * root, string s) {
    std::map<std::string, std::string> dictionary;   
    std::string binary = "";
    
    iter(root, binary, dictionary);
    
    binary="";
    
    for (char c : s){
        std::string str{c};
        binary = binary+str;
    
        if (dictionary.find(binary) != dictionary.end()) {
            std::cout <<dictionary[binary];
            binary="";
        }
    }
    }
    
  • + 0 comments
    void decode(String s, Node root) {
            String word = "";
            Node location = root;
            for(char i: s.toCharArray()){
           if(i == '0'){
            if (location.left.left ==null){
                word+=location.left.data;
                location = root;
            }else{
            location = location.left;
            }
           }
           else if(i=='1'){
            if (location.right.right ==null){
                word+=location.right.data;
                location = root;
            }else{
            location = location.right;
            }
           }
           } 
           System.out.print(word);