import heapq
class Node:
    def __init__(self, ch, fr):
        self.char = ch
        self.freq = fr
        self.left = None
        self.right = None

    def __lt__(self, other):
        return self.freq < other.freq

class HuffmanCode:
    #HashMap to store the bits of every character
    codes = {}
    '''
        None is equivalent to Null
    '''
    def encode(self, root, text):
        if root is None:
            return

        if root.left is None and root.right is None:
            self.codes[root.char] = text
            return

        self.encode(root.right, text + "1")
        self.encode(root.left, text + "0")


    def decode(self, root, bitString):
        print(bitString)
        curr = root
        decodeString = ""
        for bit in bitString:
            if curr is None:
                return

            if bit == '1':
                curr = curr.right
            else:
                curr = curr.left

            if curr.left is None and curr.right is None:
                decodeString += curr.char
                curr = root

        print(decodeString)

    def buildTree(self, textString):
        queue = []
        #HashMap
        map = {}

        #Loop through the text and increment the frequnency
        for c in textString:
            if not c in map:
                map[c] = 1
            else:
                map[c] += 1

        #Loop through the map and create leaves
        for key in map:
            heapq.heappush(queue, Node(key, map[key]))

        #Loop through the queue and build the tree
        while len(queue) > 1:
            node1 = heapq.heappop(queue)
            node2 = heapq.heappop(queue)

            newNode = Node(None, node1.freq + node2.freq)

            newNode.left = node1
            newNode.right = node2

            heapq.heappush(queue, newNode)

        root = heapq.heappop(queue)
        text = ""
        self.encode(root, text)
        for key in self.codes:
            print(key, self.codes[key])

        tempString = ""
        for c in textString:
            tempString += self.codes[c]


        self.decode(root, tempString)