We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Trees
  4. Tree: Huffman Decoding
  5. Discussions

Tree: Huffman Decoding

Sort by

recency

|

546 Discussions

|

  • aritamk
     + 0 comments

    Python Recursive approach

    def get_value(node: Node, code: str, s: str, i: int) -> tuple[str, int]:
    
    if node is None:
        return code, i
        
    # leaf node
    if node.data != '\x00':
        code += str(node.data)
        return code, i
        
    if i >= len(s):
        return code, i
        
    # not leaf node
    match s[i]:
        case '0':
            return get_value(node.left, code, s, i+1)
            
        case '1':
            return get_value(node.right, code, s, i+1)
            
        case _:
            raise ValueError('Invalid Input')

    def decodeHuff(root, s):

    i: int = 0
    out_str: str = ''
    while i < len(s):
        out_str, i = get_value(root, out_str, s, i)

    print(out_str)

  • branzinho9
     + 0 comments
    void decode(String s, Node root) {        
    Node node = root;

    for (int i = 0; i < s.length(); i++) {
        node = s.charAt(i) == '0' ? node.left : node.right;

        if (node.left == null && node.right == null) {
            System.out.print(node.data);
            node = root;
        }
    }
}

  • shashank_kadapa1
     + 0 comments

    There is an error in the python's test script. The input should be encoded values, however it inputs the string.

  • vivekgupta1981
     + 0 comments

    This test code is broken for Javascript, The code was expecting that i should do encode and decode both. However question was for decoding the string and it should provide root node and encoded string. Just printing the input string passed it.

  • jnv83
     + 2 comments

    Java 8:

        private int printLeaf(int stepNum, String s, Node node) {
        if (Objects.nonNull(node.left) && s.charAt(stepNum) == '0')
            stepNum = printLeaf(stepNum + 1, s, node.left); 
        else if (Objects.nonNull(node.right) && s.charAt(stepNum) == '1')
            stepNum = printLeaf(stepNum + 1, s, node.right);
        
        System.out.print(node.data);
        return stepNum;
    }

void decode(String s, Node root) {
        int cur = 0;
        while (cur < s.length()) cur = printLeaf(cur, s, root);
    }

    Not sure what am I missing, it prints all the correct valued in the output, but shows "Wrong answer".