Tree: Huffman Decoding

  • + 0 comments

    Java, O(n)

    void decode(String s, Node root) {
            StringBuilder decodedString = new StringBuilder();
            Node current = root;
            
            for (int i = 0; i < s.length(); i++) {
                char bit = s.charAt(i);
                if (bit == '0') {
                    current = current.left;
                } else {
                    current = current.right;
                }
                
                if (current instanceof HuffmanLeaf) {
                    HuffmanLeaf leaf = (HuffmanLeaf) current;
                    decodedString.append(leaf.data);
                    current = root;
                }
            }
            
            System.out.println(decodedString.toString());
        }