Given a string S of distinct character of size N and their corresponding frequency f[ ] i.e. character S[i] has f[i] frequency. Your task is to build the Huffman tree print all the huffman codes in preorder traversal of the tree.
Note: While merging if two nodes have the same value, then the node which occurs at first will be taken on the left of Binary Tree and the other one to the right, otherwise Node with less value will be taken on the left of the subtree and other one to the right.
Example 1:
S = "abcdef"
f[] = {5, 9, 12, 13, 16, 45}
Output: 
0 100 101 1100 1101 111
Explanation:
HuffmanCodes will be:
f : 0
c : 100
d : 101
a : 1100
b : 1101
e : 111
Hence printing them in the PreOrder of Binary 
Tree.
Your Task:
You don't need to read or print anything. Your task is to complete the function huffmanCodes() which takes the given string S, frequency array f[ ] and number of characters N as input parameters and returns a vector of strings containing all huffman codes in order of preorder traversal of the tree.
Expected Time complexity: O(N * LogN) 
Expected Space complexity: O(N) 
Constraints:
1 ≤ N ≤ 26

Difficulty: MEDIUM
Tags: Data structures
Skill types: Data structures
Expected Time Complexity: O(N*LogN)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3







class Solution:

    def huffmanCodes(self,S,f,N):

        # Code here

Solutions:
from heapq import heapify, heappush, heappop

class Node:

	def __init__(self, d):
		self.data = d
		self.left = None
		self.right = None

	def __lt__(self, nxt):
		return self.data < nxt.data

class Solution:

	def huffmanCodes(self, S, f, N):
		heap = []
		for i in range(N):
			temp = Node(f[i])
			heappush(heap, temp)
		while len(heap) > 1:
			left = heappop(heap)
			right = heappop(heap)
			newNode = Node(left.data + right.data)
			newNode.left = left
			newNode.right = right
			heappush(heap, newNode)
		root = heappop(heap)
		ans = []
		temp = ''
		self.traverse(root, ans, temp)
		return ans

	def traverse(self, root, ans, temp):
		if root.left == None and root.right == None:
			ans.append(temp)
			return
		self.traverse(root.left, ans, temp + '0')
		self.traverse(root.right, ans, temp + '1')


import heapq

class Solution:

	def huffmanCodes(self, S, f, N):

		class node:

			def __init__(self, char, freq, left=None, right=None):
				self.char = char
				self.freq = freq
				self.left = left
				self.right = right
				self.huffcode = ''

			def __lt__(self, node2):
				return self.freq < node2.freq
		nodes = []
		for i in range(N):
			heapq.heappush(nodes, node(S[i], f[i]))
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			left.huffcode = '0'
			right.huffcode = '1'
			newnode = node(left.char + right.char, left.freq + right.freq, left, right)
			heapq.heappush(nodes, newnode)
		res = []

		def print(node, path=''):
			if node == None:
				return
			path = path + node.huffcode
			print(node.left, path)
			print(node.right, path)
			if node.left == None and node.right == None:
				res.append(path)
		print(nodes[0])
		return res


import heapq

class Node:

	def __init__(self, d):
		self.data = d
		self.left = None
		self.right = None

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

class Solution:

	def huffmanCodes(self, S, f, N):
		minheap = []
		for i in range(0, N):
			temp = Node(f[i])
			heapq.heappush(minheap, temp)
		while len(minheap) > 1:
			left = heapq.heappop(minheap)
			right = heapq.heappop(minheap)
			newnode = Node(left.data + right.data)
			newnode.left = left
			newnode.right = right
			heapq.heappush(minheap, newnode)
		root = minheap[0]
		temp = ''
		ans = []
		self.traverse(root, ans, temp)
		return ans

	def traverse(self, root, ans, temp):
		if root.left == None and root.right == None:
			ans.append(temp)
			return
		self.traverse(root.left, ans, temp + '0')
		self.traverse(root.right, ans, temp + '1')


import heapq

class Solution:

	class Node:

		def __init__(self, fre, symbole, left=None, right=None):
			self.freq = fre
			self.symbole = symbole
			self.right = right
			self.left = left
			self.helf = ''

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

	def huffmanCodes(self, S, f, N):
		node = []
		for i in range(N):
			heapq.heappush(node, self.Node(f[i], S[i]))
		while len(node) > 1:
			left = heapq.heappop(node)
			right = heapq.heappop(node)
			left.helf = '0'
			right.helf = '1'
			newnode = self.Node(left.freq + right.freq, left.symbole + right.symbole, left, right)
			heapq.heappush(node, newnode)
		out = []

		def getans(no, s):
			if no:
				s += no.helf
				getans(no.left, s)
				getans(no.right, s)
				if not no.left and (not no.right):
					out.append(s)
		getans(node[0], '')
		return out


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

	def __lt__(self, nxt):
		return self.data < nxt.data

class Solution:

	def traverse(self, root, path, ans):
		if root.left is None and root.right is None:
			ans.append(path)
			return
		self.traverse(root.left, path + '0', ans)
		self.traverse(root.right, path + '1', ans)

	def huffmanCodes(self, S, f, N):
		min_heap = []
		for freq in f:
			heapq.heappush(min_heap, Node(freq))
		while len(min_heap) > 1:
			left = heapq.heappop(min_heap)
			right = heapq.heappop(min_heap)
			node = Node(left.data + right.data)
			node.left = left
			node.right = right
			heapq.heappush(min_heap, node)
		root = heapq.heappop(min_heap)
		ans = []
		path = ''
		self.traverse(root, path, ans)
		return ans


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

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

class Solution:

	def traverse(self, root, ans, temp):
		if root.left == None and root.right == None:
			ans.append(temp)
			return
		self.traverse(root.left, ans, temp + '0')
		self.traverse(root.right, ans, temp + '1')

	def huffmanCodes(self, S, f, N):
		minHeap = []
		for i in range(N):
			temp = Node(f[i])
			heapq.heappush(minHeap, [f[i], temp])
		while len(minHeap) > 1:
			(dataleft, left) = heapq.heappop(minHeap)
			(dataright, right) = heapq.heappop(minHeap)
			newNode = Node(dataleft + dataright)
			heapq.heappush(minHeap, [newNode.data, newNode])
			newNode.left = left
			newNode.right = right
		ans = []
		temp = ''
		root = minHeap[0][1]
		self.traverse(root, ans, temp)
		return ans


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

	def __lt__(self, nxt):
		return self.data < nxt.data

class Solution:

	def preorder(self, root, temp, ans):
		if root and root.left == None and (root.right == None):
			ans.append(temp)
			return
		self.preorder(root.left, temp + '0', ans)
		self.preorder(root.right, temp + '1', ans)

	def huffmanCodes(self, S, f, N):
		min_heap = []
		for i in range(N):
			node = Node(f[i])
			heapq.heappush(min_heap, node)
		while len(min_heap) > 1:
			left = heapq.heappop(min_heap)
			right = heapq.heappop(min_heap)
			data = left.data + right.data
			node = Node(data)
			node.left = left
			node.right = right
			heapq.heappush(min_heap, node)
		root = heapq.heappop(min_heap)
		ans = []
		temp = ''
		self.preorder(root, temp, ans)
		return ans


from heapq import heapify, heappush, heappop

class Node:

	def __init__(self, val):
		self.left = None
		self.right = None
		self.val = val

	def __lt__(self, other):
		return self.val > other.val

class Solution:

	def huffmanCodes(self, S, f, N):
		heap = []
		for i in range(N):
			heappush(heap, (f[i], Node(f[i])))
		while len(heap) > 1:
			a = heappop(heap)
			b = heappop(heap)
			c = a[0] + b[0]
			k = Node(c)
			k.left = a[1]
			k.right = b[1]
			heappush(heap, (c, k))
		ans = []

		def pre(num, code):
			if num.left:
				pre(num.left, code + '0')
			if num.right:
				pre(num.right, code + '1')
			if not num.left and (not num.right):
				ans.append(code)
		pre(heap[0][1], '')
		return ans


import heapq

class Node:

	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None

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

class Solution:

	def huffmanCodes(self, S, f, N):
		nodes = [Node(i) for i in f]
		heapq.heapify(nodes)
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			newNode = Node(left.value + right.value)
			newNode.left = left
			newNode.right = right
			heapq.heappush(nodes, newNode)
		root = nodes[0]
		ans = []

		def preOrdertaversal(root, temp):
			if root.left == None and root.right == None:
				ans.append(temp)
				return
			preOrdertaversal(root.left, temp + '0')
			preOrdertaversal(root.right, temp + '1')
		preOrdertaversal(root, '')
		return ans


import heapq

class Solution:

	class code_node:

		def __init__(self, freq, left, right, parent, id):
			self.freq = freq
			self.left_child = left
			self.right_child = right
			self.parent = parent
			self.id = id

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

	def huffmanCodes(self, S, f, N):
		idx = 0
		node_dict = {}
		node_list = []
		for str in S:
			node = self.code_node(f[idx], None, None, None, str)
			node_dict[str] = node
			node_list.append(node)
			idx += 1
		heapq.heapify(node_list)
		while len(node_list) > 1:
			node_1 = heapq.heappop(node_list)
			node_2 = heapq.heappop(node_list)
			new_node = self.code_node(node_1.freq + node_2.freq, node_1, node_2, None, node_1.id + node_2.id)
			node_1.parent = new_node
			node_2.parent = new_node
			heapq.heappush(node_list, new_node)
		print_list = []
		self.pre_order_travel(node_list[0], print_list, '')
		return print_list

	def pre_order_travel(self, node, print_list, prefix):
		if node.left_child is None and node.right_child is None:
			print_list.append(prefix)
		else:
			if node.left_child is not None:
				l_prefix = prefix + str(0)
				self.pre_order_travel(node.left_child, print_list, l_prefix)
			if node.right_child is not None:
				r_prefix = prefix + str(1)
				self.pre_order_travel(node.right_child, print_list, r_prefix)


class node:

	def __init__(self, a, b, left=None, right=None):
		self.char = a
		self.count = b
		self.left = left
		self.right = right

	def __lt__(self, x):
		return self.count < x.count

def preorder(root, s, l):
	if root == None:
		return
	if root.char != '$':
		l.append(s)
		return
	preorder(root.left, s + '0', l)
	preorder(root.right, s + '1', l)

class Solution:

	def huffmanCodes(self, s, f, n):
		order = {}
		order['$'] = float('inf')
		for i in range(n):
			order[s[i]] = i
		import heapq
		h = []
		for i in range(n):
			heapq.heappush(h, node(s[i], f[i]))
		while len(h) > 1:
			one = heapq.heappop(h)
			two = heapq.heappop(h)
			new = node('$', one.count + two.count, one, two)
			heapq.heappush(h, new)
		root = heapq.heappop(h)
		l = []
		preorder(root, '', l)
		return l


from heapq import *

class TreeNode:

	def __init__(self, data=None):
		self.data = data
		self.left = None
		self.right = None

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

class Solution:

	def huffmanCodes(self, S, f, N):
		mini = []
		for i in range(N):
			heappush(mini, TreeNode(f[i]))
		while len(mini) != 1:
			left = heappop(mini)
			right = heappop(mini)
			tmp = TreeNode(left.data + right.data)
			tmp.left = left
			tmp.right = right
			heappush(mini, tmp)
		root = heappop(mini)
		ans = []
		self.traverse(root, ans, '')
		return ans

	def traverse(self, node, ans, tmp):
		if node.left == None and node.right == None:
			if tmp:
				ans.append(tmp)
			return
		self.traverse(node.left, ans, tmp + '0')
		self.traverse(node.right, ans, tmp + '1')


import heapq
import ctypes

class Node:

	def __init__(self, val):
		self.val = val
		self.left = None
		self.right = None

	def __lt__(self, nxt):
		return self.val < nxt.val

class Solution:

	def huffmanCodes(self, S, f, N):

		def preorder(temp, tans):
			if temp == None:
				return
			if temp.left == None and temp.right == None:
				arr.append(tans)
			preorder(temp.left, tans + '0')
			preorder(temp.right, tans + '1')
		q = []
		heapq.heapify(q)
		for i in f:
			n = Node(i)
			heapq.heappush(q, n)
		head = None
		while q:
			a = heapq.heappop(q)
			if q:
				b = heapq.heappop(q)
				n = Node(a.val + b.val)
				if a.val <= b.val:
					n.left = a
					n.right = b
				else:
					n.left = b
					n.right = a
				heapq.heappush(q, n)
			else:
				head = a
		arr = []
		preorder(head, '')
		return arr


class TreeNode:

	def __init__(self, char, freq, leftnode, rightnode):
		self.char = char
		self.freq = freq
		self.left = leftnode
		self.right = rightnode

class HeapNode:

	def __init__(self, node):
		self.node = node

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

class Solution:

	def __init__(self):
		self.Answer = []

	def Traversal(self, node, s):
		if node == None:
			return
		if node.left == None and node.right == None:
			self.Answer.append(s)
		self.Traversal(node.left, s + '0')
		self.Traversal(node.right, s + '1')

	def huffmanCodes(self, S, f, N):
		import heapq
		PQ = []
		for i in range(0, N):
			treenode = TreeNode(S[i], f[i], None, None)
			node = HeapNode(treenode)
			PQ.append(node)
		heapq.heapify(PQ)
		while len(PQ) > 1:
			node1 = PQ[0].node
			heapq.heappop(PQ)
			node2 = PQ[0].node
			heapq.heappop(PQ)
			treenode = TreeNode('', node1.freq + node2.freq, node1, node2)
			node = HeapNode(treenode)
			heapq.heappush(PQ, node)
		root = PQ[0].node
		self.Traversal(root, '')
		return self.Answer


from heapq import heapify, heappush, heappop

class Node:

	def __init__(self, data):
		self.left = None
		self.right = None
		self.data = data

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

class Solution:

	def traverse(self, root, temp_result, result):
		if root.left is None and root.right is None:
			result.append(temp_result)
			return result
		if root.left:
			self.traverse(root.left, temp_result + '0', result)
		if root.right:
			self.traverse(root.right, temp_result + '1', result)
		return result

	def huffmanCodes(self, S, f, N):
		for i in range(N):
			f[i] = Node(f[i])
		heapify(f)
		while len(f) > 1:
			left = heappop(f)
			right = heappop(f)
			root_node = Node(left.data + right.data)
			root_node.left = left
			root_node.right = right
			heappush(f, root_node)
		temp_result = ''
		result = []
		return self.traverse(root_node, temp_result, result)


from queue import PriorityQueue
import heapq

class Node:

	def __init__(self, char, freq, left=None, right=None):
		self.char = char
		self.freq = freq
		self.left = left
		self.right = right

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

class Solution:

	def huffmanCodes(self, S, f, N):
		pq = []
		for i in range(N):
			node = Node(S[i], f[i])
			node = Node(S[i], f[i])
			heapq.heappush(pq, node)
		while len(pq) > 1:
			n1 = heapq.heappop(pq)
			n2 = heapq.heappop(pq)
			new_node = Node('0', n1.freq + n2.freq, n1, n2)
			heapq.heappush(pq, new_node)
		ans = []

		def traverse(root, temp):
			if not root:
				return
			if not root.left and (not root.right):
				ans.append(temp)
				return
			traverse(root.left, temp + '0')
			traverse(root.right, temp + '1')
		root = heapq.heappop(pq)
		traverse(root, '')
		return ans


import heapq

class Solution:

	class BinaryTree:

		def __init__(self, value, freq):
			self.right = None
			self.left = None
			self.value = value
			self.freq = freq

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

		def __eq__(self, other):
			return self.freq == other.freq

	def huffmanCodes(self, S, f, N):
		codes = {}
		ans = []
		heap = []
		for i in range(N):
			binary_tree_node = self.BinaryTree(S[i], f[i])
			heapq.heappush(heap, binary_tree_node)
		while len(heap) > 1:
			binary_tree_node_1 = heapq.heappop(heap)
			binary_tree_node_2 = heapq.heappop(heap)
			freq = binary_tree_node_1.freq + binary_tree_node_2.freq
			newnode = self.BinaryTree(None, freq)
			newnode.left = binary_tree_node_1
			newnode.right = binary_tree_node_2
			heapq.heappush(heap, newnode)

		def buildcodes(root, bits):
			if root is None:
				return
			if root.value is not None:
				codes[root.value] = bits
				ans.append(bits)
				return
			buildcodes(root.left, bits + '0')
			buildcodes(root.right, bits + '1')
		root = heapq.heappop(heap)
		buildcodes(root, '')
		return ans


import heapq

class Node:

	def __init__(self, freq):
		self.freq = freq
		self.left = None
		self.right = None

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

class Solution:

	def huffmanCodes(self, S, f, N):

		def preorder(root, encode):
			if root.left == None and root.right == None:
				ans.append(encode)
				return
			preorder(root.left, encode + '0')
			preorder(root.right, encode + '1')
		minheap = []
		for i in range(0, N):
			node = Node(f[i])
			heapq.heappush(minheap, node)
		while len(minheap) > 1:
			left = heapq.heappop(minheap)
			right = heapq.heappop(minheap)
			mergedNode = Node(left.freq + right.freq)
			mergedNode.left = left
			mergedNode.right = right
			heapq.heappush(minheap, mergedNode)
		ans = []
		root = heapq.heappop(minheap)
		encode = ''
		preorder(root, encode)
		return ans


from heapq import heappush, heappop, heapify

class Tree:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

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

class Solution:

	def huffmanCodes(self, S, f, N):
		freq = []
		heapify(freq)
		for ele in f:
			node = Tree(ele)
			heappush(freq, node)
		while len(freq) > 1:
			ele1 = heappop(freq)
			ele2 = heappop(freq)
			node = Tree(ele1.data + ele2.data)
			node.left = ele1
			node.right = ele2
			heappush(freq, node)
		root = freq[0]
		res = []
		temp = ''
		self.traversal(root, temp, res)
		return res

	def traversal(self, root, ans, res):
		if not root.left and (not root.right):
			res.append(ans)
			return
		self.traversal(root.left, ans + '0', res)
		self.traversal(root.right, ans + '1', res)


import heapq

class node:

	def __init__(self, freq, c, left, right):
		self.freq = freq
		self.c = c
		self.left = left
		self.right = right

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

class Solution:

	def huffmanCodes(self, S, f, N):

		def recurs(root, s, ans):
			if not root.left and (not root.right):
				ans.append(s)
				return
			else:
				if root.left:
					recurs(root.left, s + str(0), ans)
				if root.right:
					recurs(root.right, s + str(1), ans)
				return
		a = []
		for (i, j) in zip(S, f):
			heapq.heappush(a, node(j, i, None, None))
		while len(a) > 1:
			l = heapq.heappop(a)
			r = heapq.heappop(a)
			new = node(l.freq + r.freq, '', l, r)
			heapq.heappush(a, new)
		m = a[0]
		ans = []
		recurs(m, '', ans)
		return ans


import heapq

class Node:

	def __init__(self, data, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right

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

class Solution:

	def traverse(self, node, path, ans):
		if not node.left and (not node.right):
			ans.append(path)
			return
		self.traverse(node.left, path + '0', ans)
		self.traverse(node.right, path + '1', ans)

	def huffmanCodes(self, s, f, n):
		mnhp = []
		for i in range(n):
			mnhp.append(Node(f[i]))
		heapq.heapify(mnhp)
		root = mnhp[0]
		while len(mnhp) > 1:
			min1 = heapq.heappop(mnhp)
			min2 = heapq.heappop(mnhp)
			temp = Node(min1.data + min2.data)
			temp.left = min1
			temp.right = min2
			heapq.heappush(mnhp, temp)
			root = temp
		ans = []
		self.traverse(root, '', ans)
		return ans


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

	def __lt__(self, node):
		return self.data < node.data

class Solution:

	def traverse(self, node, temp, ans):
		if node.left == None and node.right == None:
			ans.append(temp)
			return
		self.traverse(node.left, temp + '0', ans)
		self.traverse(node.right, temp + '1', ans)

	def huffmanCodes(self, S, f, N):
		heap = []
		for i in range(N):
			node = Node(f[i])
			heap.append(node)
		heapq.heapify(heap)
		while len(heap) > 1:
			leftNode = heapq.heappop(heap)
			rightNode = heapq.heappop(heap)
			node = Node(leftNode.data + rightNode.data)
			node.left = leftNode
			node.right = rightNode
			heapq.heappush(heap, node)
		ans = []
		self.traverse(node, '', ans)
		return ans


import heapq

class Node:

	def __init__(self, data):
		self.data = data
		self.left = None
		self.right = None

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

class Solution:

	def solve(self, root, res, curans):
		if root.left == None and root.right == None:
			res.append(curans)
			return
		self.solve(root.left, res, curans + '0')
		self.solve(root.right, res, curans + '1')

	def huffmanCodes(self, S, f, N):
		l = []
		for i in f:
			node = Node(i)
			heapq.heappush(l, node)
		while len(l) > 1:
			node1 = heapq.heappop(l)
			node2 = heapq.heappop(l)
			sum3 = node1.data + node2.data
			root = Node(sum3)
			root.left = node1
			root.right = node2
			heapq.heappush(l, root)
		root = heapq.heappop(l)
		res = []
		curans = ''
		self.solve(root, res, curans)
		return res


import queue

class TreeNode:

	def __init__(self, freq, c):
		self.freq = freq
		self.c = c
		self.left = self.right = None

	def traversal(self, d, st, res):
		if self.c:
			cur = ''.join(st)
			d[self.c] = cur
			res.append(cur)
		if self.left:
			st.append('0')
			self.left.traversal(d, st, res)
			st.pop()
		if self.right:
			st.append('1')
			self.right.traversal(d, st, res)
			st.pop()

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

class Solution:

	def huffmanCodes(self, S, f, N):
		(pq, new_node) = (queue.PriorityQueue(), None)
		ordered = sorted(list(range(N)), key=lambda i: f[i])
		f = list(map(lambda i: f[ordered[i]], ordered))
		S = list(map(lambda i: S[ordered[i]], ordered))
		for i in range(N):
			new_node = TreeNode(f[i], S[i])
			pq.put(new_node)
		while pq.qsize() > 1:
			fst = pq.get()
			snd = pq.get()
			new_freq = fst.freq + snd.freq
			new_node = TreeNode(new_freq, '')
			new_node.left = fst
			new_node.right = snd
			pq.put(new_node)
		(d, res) = ({}, [])
		new_node.traversal(d, [], res)
		return res


import heapq

class node:

	def __init__(self, freq, symbol, left=None, right=None):
		self.freq = freq
		self.symbol = symbol
		self.left = left
		self.right = right
		self.huff = ''

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

class Solution:

	def preorder(self, root, res, val=''):
		new_val = val + str(root.huff)
		if root.left:
			self.preorder(root.left, res, new_val)
		if root.right:
			self.preorder(root.right, res, new_val)
		if root.left is None and root.right is None:
			res.append(new_val)

	def huffmanCodes(self, S, f, N):
		nodes = []
		for x in range(len(S)):
			heapq.heappush(nodes, node(f[x], S[x]))
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			left.huff = 0
			right.huff = 1
			new_nodes = node(left.freq + right.freq, left.symbol + right.symbol, left, right)
			heapq.heappush(nodes, new_nodes)
		res = []
		self.preorder(nodes[0], res)
		return res


class Solution:

	def huffmanCodes(self, s, f, N):

		class Node:

			def __init__(self, data, lc=None, rc=None):
				(self.d, self.lc, self.rc) = (data, lc, rc)

			def __lt__(self, n):
				return self.d[0] < n.d[0]
		h = [Node(data=(f[i], s[i])) for i in range(N)]
		import heapq
		heapq.heapify(h)
		while len(h) > 1:
			(n1, n2) = (heapq.heappop(h), heapq.heappop(h))
			heapq.heappush(h, Node(data=(n1.d[0] + n2.d[0], -1), lc=n1, rc=n2))
		root = heapq.heappop(h)
		res = []

		def pre(root, path):
			if root:
				pre(root.lc, path + '0')
				pre(root.rc, path + '1')
				if not root.lc and (not root.rc):
					res.append(path)
		pre(root, '')
		return res


from heapq import heappop, heappush

class Node:

	def __init__(self, d):
		self.data = d
		self.left = None
		self.right = None

	def __lt__(self, nxt):
		return self.data < nxt.data

class Solution:

	def huffmanCodes(self, s, f, n):
		h = []
		for i in f:
			heappush(h, Node(i))
		while len(h) > 1:
			(left, right) = (heappop(h), heappop(h))
			par = Node(left.data + right.data)
			par.left = left
			par.right = right
			heappush(h, par)
		root = heappop(h)
		ans = []

		def preOrder(root, ans, temp):
			if root.left == None and root.right == None:
				ans.append(temp)
				return
			preOrder(root.left, ans, temp + '0')
			preOrder(root.right, ans, temp + '1')
		preOrder(root, ans, '')
		return ans


import heapq

class Node:

	def __init__(self, data):
		self.left = None
		self.right = None
		self.data = data

	def __lt__(self, nxt):
		return self.data < nxt.data

class Solution:

	def p(self, root, s, res):
		if root and (not root.left) and (not root.right):
			res.append(s)
			return
		if root:
			self.p(root.left, s + '0', res)
			self.p(root.right, s + '1', res)

	def huffmanCodes(self, S, f, N):
		heap = []
		heapq.heapify(heap)
		for i in f:
			n = Node(i)
			heapq.heappush(heap, n)
		while len(list(heap)) > 1:
			e1 = heapq.heappop(heap)
			e2 = heapq.heappop(heap)
			n = Node(e1.data + e2.data)
			heapq.heappush(heap, n)
			n.left = e1
			n.right = e2
		res = []
		s = ''
		root = heapq.heappop(heap)
		self.p(root, s, res)
		return res


from heapq import heappush as push, heappop as pop

class Node(object):

	def __init__(self, x):
		self.left = None
		self.right = None
		self.data = x

	def __lt__(self, nxt):
		return self.data < nxt.data

def traverse(root, ans, temp):
	if root.left == None and root.right == None:
		ans.append(temp)
		return
	traverse(root.left, ans, temp + '0')
	traverse(root.right, ans, temp + '1')

class Solution:

	def huffmanCodes(self, S, f, N):
		h = []
		for i in f:
			n = Node(i)
			push(h, n)
		while len(h) > 1:
			na = pop(h)
			nb = pop(h)
			c = na.data + nb.data
			nc = Node(c)
			nc.left = na
			nc.right = nb
			push(h, nc)
		curr = h[0]
		ans = []
		co = ''
		traverse(curr, ans, co)
		return ans


import heapq

class node:

	def __init__(self, freq, symbol, left=None, right=None):
		self.freq = freq
		self.symbol = symbol
		self.left = left
		self.right = right
		self.huff = ''

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

def preOrderNodes(node, res, val=''):
	newVal = val + str(node.huff)
	if node.left:
		preOrderNodes(node.left, res, newVal)
	if node.right:
		preOrderNodes(node.right, res, newVal)
	if not node.left and (not node.right):
		res.append(newVal)

class Solution:

	def huffmanCodes(self, S, f, N):
		nodes = []
		for x in range(len(S)):
			heapq.heappush(nodes, node(f[x], S[x]))
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			left.huff = 0
			right.huff = 1
			newNode = node(left.freq + right.freq, left.symbol + right.symbol, left, right)
			heapq.heappush(nodes, newNode)
		res = []
		preOrderNodes(nodes[0], res)
		return res


import heapq

class Node:

	def __init__(self, frq, char, left=None, right=None):
		self.left = left
		self.right = right
		self.frq = frq
		self.char = char

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

class Solution:

	def huffmanCodes(self, S, F, N):
		heap = []
		for (c, f) in zip(S, F):
			heap.append(Node(f, c))
		heapq.heapify(heap)
		while len(heap) > 1:
			e1 = heapq.heappop(heap)
			e2 = heapq.heappop(heap)
			heapq.heappush(heap, Node(e1.frq + e2.frq, None, e1, e2))
		ans = []

		def preorder(node, prestr=''):
			if node.char is not None:
				ans.append(prestr)
				return
			preorder(node.left, prestr + '0')
			preorder(node.right, prestr + '1')
		preorder(heap[0])
		return ans


import heapq

class Node:

	def __init__(self, val):
		self.data = val
		self.left = None
		self.right = None

	def __lt__(self, nxt):
		return self.data < nxt.data

class Solution:

	def huffmanCodes(self, s, f, N):

		def traverse(root, ans, strg):
			if root.left == None and root.right == None:
				ans.append(strg)
				return
			traverse(root.left, ans, strg + '0')
			traverse(root.right, ans, strg + '1')
		heap = []
		for i in range(N):
			temp = Node(f[i])
			heapq.heappush(heap, temp)
		while len(heap) > 1:
			first = heapq.heappop(heap)
			second = heapq.heappop(heap)
			newNode = Node(first.data + second.data)
			newNode.left = first
			newNode.right = second
			heapq.heappush(heap, newNode)
		root = heapq.heappop(heap)
		ans = []
		temp = ''
		traverse(root, ans, temp)
		return ans


import heapq

class node:

	def __init__(self, freq, symbol, left=None, right=None):
		self.freq = freq
		self.symbol = symbol
		self.left = left
		self.right = right
		self.code = ''

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

class Solution:

	def generateCodes(self, node, curr, ans):
		if node.left:
			self.generateCodes(node.left, curr + node.code, ans)
		if node.right:
			self.generateCodes(node.right, curr + node.code, ans)
		if not node.left and (not node.right):
			ans.append(curr + node.code)

	def huffmanCodes(self, S, f, N):
		chars = list(S)
		n = len(f)
		nodes = []
		for i in range(n):
			heapq.heappush(nodes, node(f[i], chars[i]))
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			left.code = '0'
			right.code = '1'
			newNode = node(left.freq + right.freq, left.symbol + right.symbol, left, right)
			heapq.heappush(nodes, newNode)
		d = {}
		ans = []
		self.generateCodes(nodes[0], '', ans)
		return ans


import heapq

class Solution:

	def huffmanCodes(self, S, f, N):

		class node:

			def __init__(self, val, symbol, left=None, right=None):
				self.val = val
				self.symbol = symbol
				self.left = left
				self.right = right
				self.huff = ''

			def __lt__(self, nxt):
				return self.val < nxt.val
		res = []
		heap = []
		for i in range(N):
			heapq.heappush(heap, node(f[i], S[i]))
		while len(heap) > 1:
			min1 = heapq.heappop(heap)
			min2 = heapq.heappop(heap)
			min1.huff = 0
			min2.huff = 1
			newnode = node(min1.val + min2.val, min1.symbol + min2.symbol, min1, min2)
			heapq.heappush(heap, newnode)

		def gethuff(heap, huffval):
			newval = huffval + str(heap.huff)
			if heap.left:
				gethuff(heap.left, newval)
			if heap.right:
				gethuff(heap.right, newval)
			if not heap.left and (not heap.right):
				res.append(newval)
		gethuff(heap[0], '')
		return res


import heapq

class node:

	def __init__(self, freq, symbol, left=None, right=None):
		self.freq = freq
		self.symbol = symbol
		self.left = left
		self.right = right
		self.huff = ''

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

class Solution:

	def huffmanCodes(self, S, f, N):
		nodes = []
		for x in range(len(S)):
			heapq.heappush(nodes, node(f[x], S[x]))
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			left.huff = 0
			right.huff = 1
			newnode = node(left.freq + right.freq, left.symbol + right.symbol, left, right)
			heapq.heappush(nodes, newnode)
		ans = []
		self.printNodes(nodes[0], ans)
		return ans

	def printNodes(self, node, ans, val=''):
		newval = val + str(node.huff)
		if node.left:
			self.printNodes(node.left, ans, newval)
		if node.right:
			self.printNodes(node.right, ans, newval)
		if not node.left and (not node.right):
			ans.append(newval)


import heapq

class Node:

	def __init__(self, ch, freq):
		self.ch = ch
		self.freq = freq
		self.left = None
		self.right = None

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

	def __eq__(self, other):
		return isinstance(other, Node) and self.freq == other.freq

class Solution:

	def preOrder(self, traversal, root, codeStr):
		if root == None:
			return
		if root.ch != None:
			traversal.append(''.join(codeStr))
			return
		codeStr.append('0')
		self.preOrder(traversal, root.left, codeStr)
		codeStr.pop()
		codeStr.append('1')
		self.preOrder(traversal, root.right, codeStr)
		codeStr.pop()

	def huffmanCodes(self, S, f, N):
		h = []
		for i in range(N):
			h.append(Node(S[i], f[i]))
		heapq.heapify(h)
		while len(h) > 1:
			first = heapq.heappop(h)
			second = heapq.heappop(h)
			res = Node(None, first.freq + second.freq)
			res.left = first
			res.right = second
			heapq.heappush(h, res)
		traversal = []
		codeStr = []
		self.preOrder(traversal, heapq.heappop(h), codeStr)
		return traversal


class node:

	def __init__(self, value):
		self.data = value
		self.left = None
		self.right = None

def heapify(a, i, n):
	Min = i
	l = 2 * i + 1
	r = l + 1
	if l < n and a[l].data <= a[Min].data:
		Min = l
	if r < n and a[r].data <= a[Min].data:
		Min = r
	if Min != i:
		(a[i], a[Min]) = (a[Min], a[i])
		heapify(a, Min, n)

def insertHeap(a, n, key):
	i = n
	a[i] = key
	while i > 0:
		p = (i - 1) // 2
		if a[p].data > a[i].data:
			(a[p], a[i]) = (a[i], a[p])
			i = p
		else:
			break

def preorder(root, prev, ans):
	if root:
		if not root.left and (not root.right):
			ans.append(prev)
			return
		preorder(root.left, prev + '0', ans)
		preorder(root.right, prev + '1', ans)

class Solution:

	def huffmanCodes(self, S, f, N):
		heap = []
		for e in f:
			heap.append(node(e))
		for e in range(len(heap) - 1):
			t1 = heap[0]
			heap[0] = heap[N - 1]
			heapify(heap, 0, N - 1)
			t2 = heap[0]
			heap[0] = heap[N - 2]
			heapify(heap, 0, N - 2)
			temp = node(t1.data + t2.data)
			temp.left = t1
			temp.right = t2
			insertHeap(heap, N - 2, temp)
			N -= 1
		root = heap[0]
		ans = []
		preorder(root, '', ans)
		return ans


class Node:

	def __init__(self, data, freq):
		self.data = data
		self.freq = freq
		self.left = None
		self.right = None

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

class Solution:

	def get_codes(self, root, s, res):
		if root is None:
			return
		if root.data != '$':
			res.append(s)
			return
		self.get_codes(root.left, s + '0', res)
		self.get_codes(root.right, s + '1', res)

	def huffmanCodes(self, S, f, N):
		min_heap = []
		for i in range(N):
			node = Node(S[i], f[i])
			min_heap.append(node)
		heapq.heapify(min_heap)
		while len(min_heap) > 1:
			left = heapq.heappop(min_heap)
			right = heapq.heappop(min_heap)
			top = Node('$', left.freq + right.freq)
			top.left = left
			top.right = right
			heapq.heappush(min_heap, top)
		root = heapq.heappop(min_heap)
		res = []
		self.get_codes(root, '', res)
		return res


import heapq

class Node:

	def __init__(self, freq, val=None, left=None, right=None):
		self.freq = freq
		self.val = val
		self.left = left
		self.right = right

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

class Solution:

	def huffmanCodes(self, S, f, N):
		heap = []
		heapq.heapify(heap)
		for i in range(N):
			heapq.heappush(heap, Node(f[i], S[i]))
		while len(heap) > 1:
			l = heapq.heappop(heap)
			r = heapq.heappop(heap)
			heapq.heappush(heap, Node(l.freq + r.freq, None, l, r))
		root = heapq.heappop(heap)
		ans = []

		def traverse(root, code):
			if not root:
				return
			if root.val:
				ans.append(code)
			traverse(root.left, code + '0')
			traverse(root.right, code + '1')
		traverse(root, '')
		return ans


import heapq

class node:

	def __init__(self, freq, symbol, left=None, right=None):
		self.freq = freq
		self.symbol = symbol
		self.left = left
		self.right = right
		self.huff = ''

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

class Solution:
	res = []

	def traverse(self, node, res, val=''):
		newval = val + str(node.huff)
		if node.left:
			self.traverse(node.left, res, newval)
		if node.right:
			self.traverse(node.right, res, newval)
		if not node.left and (not node.right):
			res.append(newval)

	def huffmanCodes(self, S, f, N):
		self.res = []
		S = list(S)
		nodes = []
		for i in range(N):
			heapq.heappush(nodes, node(f[i], S[i]))
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			left.huff = 0
			right.huff = 1
			newnode = node(left.freq + right.freq, left.symbol + right.symbol, left, right)
			heapq.heappush(nodes, newnode)
		self.traverse(nodes[0], self.res)
		return self.res


import heapq

class Node:

	def __init__(self, val, char='', left=None, right=None) -> None:
		self.char = char
		self.val = val
		self.left = left
		self.right = right

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

class Solution:

	def __init__(self) -> None:
		self.encodings = []

	def dfs(self, root, encodingArr):
		if not root:
			return
		if not root.left and (not root.right):
			self.encodings.append(''.join(encodingArr))
			return
		encodingArr.append('0')
		self.dfs(root.left, encodingArr)
		encodingArr.pop()
		encodingArr.append('1')
		self.dfs(root.right, encodingArr)
		encodingArr.pop()

	def huffmanCodes(self, s, f, n):
		minHeap = []
		for i in range(n):
			minHeap.append(Node(f[i], s[i]))
		heapq.heapify(minHeap)
		while len(minHeap) > 1:
			left = minHeap[0]
			heapq.heappop(minHeap)
			right = minHeap[0]
			heapq.heappop(minHeap)
			newNode = Node(left.val + right.val)
			newNode.left = left
			newNode.right = right
			heapq.heappush(minHeap, newNode)
		root = minHeap[0]
		encodingArr = []
		self.dfs(root, encodingArr)
		return self.encodings


class Node:

	def __init__(self, frequency, symbol, left=None, right=None):
		self.frequency = frequency
		self.symbol = symbol
		self.left = left
		self.right = right
		self.code = ''

	def __lt__(self, next):
		return self.frequency < next.frequency

class Solution:

	def print_preorder(self, parent, codes, res):
		if parent.left:
			self.print_preorder(parent.left, codes + parent.left.code, res)
		if parent.right:
			self.print_preorder(parent.right, codes + parent.right.code, res)
		if not parent.left and (not parent.right):
			res.append(codes)

	def huffmanCodes(self, S, f, N):
		import heapq
		nodes = []
		for i in range(N):
			heapq.heappush(nodes, Node(f[i], S[i]))
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			left.code = '0'
			right.code = '1'
			heapq.heappush(nodes, Node(left.frequency + right.frequency, left.symbol + right.symbol, left=left, right=right))
		res = []
		self.print_preorder(nodes[0], '', res)
		return res


import heapq

class BinaryTreeNode:

	def __init__(self, value, freq):
		self.value = value
		self.freq = freq
		self.left = self.right = None

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

class Solution:

	def buildTree(self, heap):
		while len(heap) > 1:
			nodeleft = heapq.heappop(heap)
			noderight = heapq.heappop(heap)
			newFreq = nodeleft.freq + noderight.freq
			parentNode = BinaryTreeNode(None, newFreq)
			parentNode.left = nodeleft
			parentNode.right = noderight
			heapq.heappush(heap, parentNode)
		return

	def buildcodes(self, root, currbits, ans):
		if root is None:
			return
		if root.value is not None:
			ans.append(currbits)
		self.buildcodes(root.left, currbits + '0', ans)
		self.buildcodes(root.right, currbits + '1', ans)

	def huffmanCodes(self, S, f, N):
		heap = []
		for i in range(len(S)):
			value = S[i]
			freq = f[i]
			newNode = BinaryTreeNode(value, freq)
			heapq.heappush(heap, newNode)
		self.buildTree(heap)
		root = heapq.heappop(heap)
		ans = []
		self.buildcodes(root, '', ans)
		return ans


from heapq import heapify, heappush, heappop

class Node:

	def __init__(self, freq, symbol, left=None, right=None):
		self.freq = freq
		self.symbol = symbol
		self.left = left
		self.right = right

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

class Solution:

	def traverse(self, root, ans, curr):
		if root == None:
			return
		if root.symbol != '$' and root.left == None and (root.right == None):
			ans.append(curr)
			return
		self.traverse(root.left, ans, curr + '0')
		self.traverse(root.right, ans, curr + '1')

	def huffmanCodes(self, S, f, N):
		heap = []
		heapify(heap)
		for i in range(N):
			heappush(heap, Node(f[i], S[i]))
		while len(heap) > 1:
			left = heappop(heap)
			right = heappop(heap)
			node = Node(left.freq + right.freq, '$', left, right)
			heappush(heap, node)
		ans = []
		self.traverse(heappop(heap), ans, '')
		return ans


import heapq

class Node:

	def __init__(self, value):
		self.value = value
		self.left = None
		self.right = None

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

class Solution:

	def traverse(self, root, ans, path):
		if root.left is None and root.right is None:
			ans.append(path)
			return
		self.traverse(root.left, ans, path + '0')
		self.traverse(root.right, ans, path + '1')

	def huffmanCodes(self, S, f, N):
		heap = []
		for i in range(N):
			node = Node(f[i])
			heapq.heappush(heap, node)
		while len(heap) > 1:
			left = heapq.heappop(heap)
			right = heapq.heappop(heap)
			parentNode = Node(left.value + right.value)
			parentNode.left = left
			parentNode.right = right
			heapq.heappush(heap, parentNode)
		ans = []
		root = heapq.heappop(heap)
		path = ''
		self.traverse(root, ans, path)
		return ans


import heapq

class node:

	def __init__(self, freq, symbol, left=None, right=None):
		self.freq = freq
		self.symbol = symbol
		self.left = left
		self.right = right
		self.huff = ''

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

class Solution:

	def huffmanCodes(self, S, f, N):
		nodes = []
		for a in range(len(f)):
			heapq.heappush(nodes, node(f[a], S[a]))
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			left.huff = '0'
			right.huff = '1'
			newnode = node(left.freq + right.freq, left.symbol + right.symbol, left, right)
			heapq.heappush(nodes, newnode)
		l = []
		self.p(nodes[0], l)
		return l

	def p(self, node, l, var=''):
		newvar = var + node.huff
		if node.left:
			self.p(node.left, l, newvar)
		if node.right:
			self.p(node.right, l, newvar)
		if not node.left and (not node.right):
			l.append(newvar)


import heapq

class Node:

	def __init__(self, freq, ch, left=None, right=None):
		self.freq = freq
		self.ch = ch
		self.left = left
		self.right = right
		self.dir = ''

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

class Solution:

	def huffmanCodes(self, s, f, n):
		res = []
		for i in range(n):
			heapq.heappush(res, Node(f[i], s[i]))
		while len(res) != 1:
			l = heapq.heappop(res)
			r = heapq.heappop(res)
			l.dir = 0
			r.dir = 1
			heapq.heappush(res, Node(l.freq + r.freq, l.ch + r.ch, l, r))

		def traverse(res, val='', ans=[]):
			newval = val + str(res.dir)
			if res.left:
				traverse(res.left, newval, ans)
			if res.right:
				traverse(res.right, newval, ans)
			if not res.right and (not res.left):
				ans.append(newval)
			return ans
		return traverse(res[0])


class Node:

	def __init__(self, value=None, path=None, left=None, right=None):
		self.value = value
		self.path = path
		self.left = left
		self.right = right

	def __lt__(self, x):
		return x.value < self.value
import heapq

class Solution:

	def huffmanCodes(self, S, f, N):
		if N < 2:
			return 0
		heap = [(n, Node(value=n)) for n in f]
		heapq.heapify(heap)
		while len(heap) >= 2:
			(v1, n1) = heapq.heappop(heap)
			(v2, n2) = heapq.heappop(heap)
			(n1.path, n2.path) = ('0', '1')
			v3 = v1 + v2
			n3 = Node(value=v3)
			n3.left = n1
			n3.right = n2
			heapq.heappush(heap, (v3, n3))
		(_, root) = heapq.heappop(heap)
		ans = []

		def dfs(root, path):
			if not root:
				return
			if root.path:
				path += root.path
			if not root.left and (not root.right):
				ans.append(path)
			dfs(root.left, path)
			dfs(root.right, path)
		dfs(root, '')
		return ans


from heapq import heappush as hpush, heappop as hpop, heapify

class Node:

	def __init__(self, f, c=None):
		self.freq = f
		self.char = c
		self.left = None
		self.right = None

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

class Solution:

	def huffmanCodes(self, S, f, N):
		heap = [Node(f[i], S[i]) for i in range(N)]
		heapify(heap)
		while len(heap) != 1:
			left = hpop(heap)
			right = hpop(heap)
			parent = Node(left.freq + right.freq)
			parent.left = left
			parent.right = right
			hpush(heap, parent)
		root = hpop(heap)

		def preorder(root, path=''):
			if not root.left and (not root.right):
				preorder.res.append(path)
			if root.left:
				preorder(root.left, path + '0')
			if root.right:
				preorder(root.right, path + '1')
		preorder.res = []
		preorder(root)
		return preorder.res


import heapq
from functools import total_ordering

class Node(object):

	def __init__(self, freq, char=None, left=None, right=None):
		self.freq = freq
		self.char = char
		self.left = left
		self.right = right

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

	def __eq__(self, other):
		return self.freq == other.freq

	def __str__(self):
		return '(' + str(self.freq) + ', ' + self.char + ')'

	def __repr__(self):
		return str(self)

def getCodes(root):
	ans = []

	def recurse(cur, path=''):
		if not cur.left and (not cur.right):
			ans.append(path)
		if cur.left:
			recurse(cur.left, path + '0')
		if cur.right:
			recurse(cur.right, path + '1')
	recurse(root)
	return ans

class Solution:

	def huffmanCodes(self, chars, freqs, n):
		heap = []
		for (c, f) in zip(chars, freqs):
			heapq.heappush(heap, Node(f, c))
		while len(heap) > 1:
			node1 = heapq.heappop(heap)
			node2 = heapq.heappop(heap)
			heapq.heappush(heap, Node(node1.freq + node2.freq, None, node1, node2))
		return getCodes(heap[0])


import heapq

class Node:

	def __init__(self, sym, freq, left=None, right=None):
		self.sym = sym
		self.freq = freq
		self.left = left
		self.right = right
		self.huff = ''

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

class Solution:

	def huffmanCodes(self, S, f, N):

		def huffmantree(node, res, val=''):
			val = val + str(node.huff)
			if node.left:
				huffmantree(node.left, res, val)
			if node.right:
				huffmantree(node.right, res, val)
			if not node.left and (not node.right):
				res.append(val)
		chars = S
		freqs = f
		nodes = []
		for i in range(len(f)):
			heapq.heappush(nodes, Node(chars[i], freqs[i]))
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			left.huff = 0
			right.huff = 1
			parent = Node(left.sym + right.sym, left.freq + right.freq, left, right)
			heapq.heappush(nodes, parent)
		res = []
		huffmantree(nodes[0], res)
		return res


import heapq

class Node:

	def __init__(self, freq, symbol, left=None, right=None):
		self.freq = freq
		self.symbol = symbol
		self.left = left
		self.right = right
		self.huff = ''

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

class Solution:

	def search(self, root, path):
		if root.left == None and root.right == None:
			self.res.append(path)
			return
		else:
			self.search(root.left, path + '0')
			self.search(root.right, path + '1')
			return

	def huffmanCodes(self, S, f, N):
		minheap = []
		self.res = []
		S = list(S)
		self.nodemap = {}
		count = 0
		for i in range(len(S)):
			ch = S[i]
			freq = f[i]
			node = Node(freq=freq, symbol=ch)
			heapq.heappush(minheap, node)
		while len(minheap) != 1:
			left = heapq.heappop(minheap)
			right = heapq.heappop(minheap)
			freq = left.freq + right.freq
			node = Node(freq, '', left, right)
			heapq.heappush(minheap, node)
		root = heapq.heappop(minheap)
		self.search(root, '')
		return self.res


from heapq import heappush, heappop

class Node:

	def __init__(self, char, freq, left=None, right=None):
		self.symbol = char
		self.left = right
		self.right = left
		self.freq = freq
		self.huff = ''

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

class Solution:

	def preorder(self, root, l, val):
		if root is None:
			return
		else:
			newval = val + str(root.huff)
			if root.left is None and root.right is None:
				l.append(newval)
			self.preorder(root.left, l, newval)
			self.preorder(root.right, l, newval)

	def huffmanCodes(self, S, f, N):
		nodes = []
		for i in range(N):
			heappush(nodes, Node(S[i], f[i]))
		while len(nodes) > 1:
			left = heappop(nodes)
			right = heappop(nodes)
			left.huff = 0
			right.huff = 1
			newnode = Node(left.symbol + right.symbol, left.freq + right.freq, left, right)
			heappush(nodes, newnode)
		l = []
		self.preorder(nodes[0], l, '')
		l.reverse()
		return l


import heapq

class Solution:

	def huffmanCodes(self, S, f, N):
		root = self.buildtree(S, f, N)
		code = []
		self.ans = []
		self.traverse(root, code)
		return self.ans

	def buildtree(self, S, f, N):
		temparr = [Tree(freq, char) for (freq, char) in zip(f, list(S))]
		heapq.heapify(temparr)
		while len(temparr) > 1:
			leftnode = heapq.heappop(temparr)
			rightnode = heapq.heappop(temparr)
			temptree = Tree(leftnode.freq + rightnode.freq, None, left=leftnode, right=rightnode)
			heapq.heappush(temparr, temptree)
		return heapq.heappop(temparr)

	def traverse(self, root, code):
		if root == None:
			return
		if root.left == None and root.right == None:
			self.ans.append(''.join(code))
			return
		else:
			code.append('0')
			self.traverse(root.left, code)
			code.pop()
			code.append('1')
			self.traverse(root.right, code)
			code.pop()
			return

class Tree:

	def __init__(self, freq, char, left=None, right=None):
		self.freq = freq
		self.char = char
		self.left = left
		self.right = right

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


class Solution:

	def huffmanCodes(self, s, f, N):

		class node:

			def __init__(self, ch, f, left=None, right=None):
				self.ch = [c for c in ch]
				self.freq = f
				self.left = left
				self.right = right

			def __lt__(self, other):
				return self.freq < other.freq
		import heapq
		nodes = [node(s[i], f[i]) for i in range(len(s))]
		heapq.heapify(nodes)
		while len(nodes) > 1:
			left = heapq.heappop(nodes)
			right = heapq.heappop(nodes)
			new_f = left.freq + right.freq
			heapq.heappush(nodes, node(left.ch + right.ch, left.freq + right.freq, left, right))
		ans = []

		def inorder(root, curr):
			if not root:
				return
			if not root.left and (not root.right):
				ans.append(''.join(curr))
				return
			curr.append('0')
			inorder(root.left, curr)
			curr.pop()
			curr.append('1')
			inorder(root.right, curr)
			curr.pop()
		root = heapq.heappop(nodes)
		inorder(root, [])
		return ans


import heapq

class huffnode:

	def __init__(self, c, f):
		self.c = c
		self.f = f
		self.left = None
		self.right = None

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

def getcodes(node, r, code=''):
	if node is None:
		return
	if node.c != '#':
		r.append(code)
	getcodes(node.left, r, code + '0')
	getcodes(node.right, r, code + '1')

class Solution:

	def huffmanCodes(self, S, f, N):
		minheap = [huffnode(S[i], f[i]) for i in range(N)]
		while len(minheap) != 1:
			left = heapq.heappop(minheap)
			right = heapq.heappop(minheap)
			t = huffnode('#', left.f + right.f)
			t.left = left
			t.right = right
			heapq.heappush(minheap, t)
		r = []
		getcodes(minheap[0], r)
		return r