Given a encoded binary string and a Huffman MinHeap tree, your task is to complete the function decodeHuffmanData(), which decodes the binary encoded string and return the original string. 
Note: Each node of the min heap contains 2 data members, a character and an integer to denote its frequency. The character '$' is the special character used for internal nodes whose min heap node only need a integer field.
Example 1:
Input :
binaryString = 
1111111111110001010101010100010010101010101
Min Heap Tree =  
                $(20)
              /      \
            /          \
         $(8)            \
       /     \             \
    $(3)      \            $(12)
    /  \       \           /    \
B(1)    D(2)    E(5)    C(6)    A(6)
Output: AAAAAABCCCCCCDDEEEEE
Explanation:
The following chart can be made from the 
given min heap tree.
character    frequency    code
    A             6        11               
    B             1        000
    C             6        10
    D             2        001    
    E             5        01
Example 2:
Input :
binaryString =
01110100011111000101101011101000111
Min Heap Tree =  
                         $(13)
                      /        \
                    /            \
                  /                \
               $(5)                  \
             /      \                  \
            /        \                   \
         $(3)         \                  $(8)
        /    \         \                /    \
     $(2)     \         \            $(4)     \
    /   \      \         \          /   \      \
f(1)    o(1)    r(1)    g(2)    k(2)    s(2)    e(4)
Output: geeksforgeeks
Explanation:
The following chart can be made from the 
given min heap tree.
character    frequency    code
    f             1        0000                 
    o             1        0001
    r             1        001
    g             2        01    
    k             2        100
    s             2        101
    e             4        11
Your Task:  
You dont need to read input or print anything. Complete the function decodeHuffmanData() which takes the root of the Huffman min heap tree and the encoded Binary String as input parameters and returns the decoded string.
Expected Time Complexity: O(N log N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^3

Source: geeksforgeeks | Difficulty: EASY
Tags: Greedy algorithms

Starter code: #User function Template for python3

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


#Function to return the decoded string.
def decodeHuffmanData(root, binaryString):
    #your code here

Solutions:
def decodeHuffmanData(root, binaryString):
	length = len(binaryString)
	head = root
	i = 0
	stringAns = ''
	while i < length:
		char = binaryString[i]
		if char == '0' and root.data == '$':
			root = root.left
			i += 1
		elif char == '1' and root.data == '$':
			root = root.right
			i += 1
		elif root.left is None and root.right is None:
			stringAns += root.data
			root = head
	stringAns += root.data
	return stringAns


def decodeHuffmanData(root, binaryString):
	ans = ''
	curr = root
	for i in range(0, len(binaryString)):
		if binaryString[i] == '0':
			curr = curr.left
		else:
			curr = curr.right
		if curr.left == None and curr.right == None:
			ans += curr.data
			curr = root
	return ans


def decodeHuffmanData(root, binaryString):
	n = root
	arr = []
	for i in binaryString:
		if i == '1':
			n = n.right
			if n.data != '$':
				arr.append(n.data)
				n = root
		if i == '0':
			n = n.left
			if n.data != '$':
				arr.append(n.data)
				n = root
	str1 = ''.join(arr)
	return str1


def decodeHuffmanData(root, binaryString):
	result = ''
	curr = root
	for char in binaryString:
		if char == '0':
			curr = curr.left
		else:
			curr = curr.right
		if curr.data != '$':
			result += curr.data
			curr = root
	return result


def decodeHuffmanData(root, binaryString):
	t = root
	res = []
	for c in binaryString:
		if c is '0':
			t = t.left
		else:
			t = t.right
		if t.left is None and t.right is None:
			res.append(t.data)
			t = root
	return ''.join(res)


def decodeHuffmanData(root, binaryString):
	output = ''
	node = root
	for item in binaryString:
		if node.data != '$':
			output += node.data
			node = root
		if item == '1':
			node = node.right
		else:
			node = node.left
	return output + node.data


def decodeHuffmanData(root, binaryString):
	res = ''
	cur = root
	for i in range(len(binaryString)):
		if binaryString[i] == '1':
			cur = cur.right
		else:
			cur = cur.left
		if not cur.left and (not cur.right):
			res += cur.data
			cur = root
	return res


def decodeHuffmanData(root, binaryString):
	t = root
	ans = []
	for i in binaryString:
		if i is '0':
			t = t.left
		else:
			t = t.right
		if t.left is None and t.right is None:
			ans.append(t.data)
			t = root
	return ''.join(ans)


def rec(root, st, s):
	if root == None:
		return
	if root.data != '$':
		s[st] = root.data
	rec(root.left, st + '0', s)
	rec(root.right, st + '1', s)

def decodeHuffmanData(root, binaryString):
	s = {}
	r = root
	rec(r, '', s)
	res = ''
	st = ''
	for i in binaryString:
		st += i
		if st in s:
			res += s[st]
			st = ''
	return res


def decodeHuffmanData(root, binaryString):
	t = root
	res = []
	for i in binaryString:
		if i == '1':
			t = t.right
		else:
			t = t.left
		if t.left == None and t.right == None:
			res.append(t.data)
			t = root
	return ''.join(res)


def decodeHuffmanData(root, binaryString):
	temp = root
	res = []
	for i in binaryString:
		if i == '0':
			temp = temp.left
		else:
			temp = temp.right
		if temp.left is None and temp.right is None:
			res.append(temp.data)
			temp = root
	return ''.join(res)


def decodeHuffmanData(root, binaryString):
	res = []
	curr = root
	for b in binaryString:
		if b == '0':
			curr = curr.left
		else:
			curr = curr.right
		if curr.data != '$':
			res.append(curr.data)
			curr = root
	return ''.join(res)


def decodeHuffmanData(root, binaryString):
	curr = root
	res = ''
	for i in binaryString:
		if i == '0':
			curr = curr.left
			if curr.data != '$':
				res += curr.data
				curr = root
		else:
			curr = curr.right
			if curr.data != '$':
				res += curr.data
				curr = root
	return res


def decodeHuffmanData(root, binaryString):
	my_dict = {}

	def trav(root, path):
		if not root:
			return
		if root.data != '$':
			my_dict[path] = [root.data, root.freq]
		trav(root.left, path + '0')
		trav(root.right, path + '1')
	trav(root, '')
	res = ''
	p = ''
	(i, j) = (0, 0)
	l = len(binaryString)
	while j < l + 1:
		c = binaryString[i:j + 1]
		if c in my_dict:
			res += my_dict[c][0]
			i = j + 1
		j += 1
	return res


def solve(root, dict1, s):
	if root == None:
		return
	if root.data != '$':
		dict1[s] = root.data
		return
	solve(root.left, dict1, s + '0')
	solve(root.right, dict1, s + '1')

def decodeHuffmanData(root, binaryString):
	dict1 = {}
	solve(root, dict1, '')
	ans = ''
	s = ''
	for i in range(len(binaryString)):
		s = s + binaryString[i]
		if s in dict1:
			ans += dict1[s]
			s = ''
	return ans


def decodeHuffmanData(root, binaryString):
	d = {}
	preOrder(root, d)
	s = ''
	res = ''
	for i in binaryString:
		s += i
		if s in d:
			res += d[s]
			s = ''
	return res

def preOrder(root, d, s=''):
	if not root:
		return
	elif root.data != '$':
		d[s] = root.data
	else:
		preOrder(root.left, d, s + '0')
		preOrder(root.right, d, s + '1')


def decodeHuffmanData(root, binaryString):
	myDict = {}
	preOrder(root, myDict)
	s = ''
	ans = ''
	for i in binaryString:
		s += i
		if s in myDict:
			ans += myDict[s]
			s = ''
	return ans

def preOrder(root, myDict, s=''):
	if not root:
		return
	elif root.data != '$':
		myDict[s] = root.data
	else:
		preOrder(root.left, myDict, s + '0')
		preOrder(root.right, myDict, s + '1')


def decodeHuffmanData(root, binaryString):
	temp = root
	res = []
	for ch in range(len(binaryString)):
		if binaryString[ch] == '0':
			temp = temp.left
		else:
			temp = temp.right
		if temp.left is None and temp.right is None:
			res.append(temp.data)
			temp = root
	return ''.join(res)


def decode(root, d, s):
	if root == None:
		return
	if root.data != '$':
		d[s] = root.data
	decode(root.left, d, s + '0')
	decode(root.right, d, s + '1')

def decodeHuffmanData(root, binaryString):
	d = {}
	decode(root, d, '')
	i = 0
	j = i + 1
	res = ''
	x = ''
	for i in binaryString:
		x += i
		if x in d:
			res += d[x]
			x = ''
	return res


def decodeHuffmanData(root, binaryString):
	i = 0
	temp = root
	ans = ''
	while i < len(binaryString):
		if binaryString[i] == '0':
			temp = temp.left
		else:
			temp = temp.right
		i += 1
		if temp.data != '$':
			ans += temp.data
			temp = root
	return ans


def decodeHuffmanData(root, binaryString):
	res = ''
	temp = root
	result = ''
	for i in binaryString:
		if i == '0':
			temp = temp.left
			if temp.data != '$':
				result += temp.data
				temp = root
		else:
			temp = temp.right
			if temp.data != '$':
				result += temp.data
				temp = root
	return result


def decodeHuffmanData(root, binaryString):
	temp = root
	result = ''
	for i in binaryString:
		if i == '0':
			temp = temp.left
			if temp.data != '$':
				result += temp.data
				temp = root
		else:
			temp = temp.right
			if temp.data != '$':
				result += temp.data
				temp = root
	return result
import heapq
minheap = []
heapq.heapify(minheap)
cnt = 0
codes = {}
freq = {}

class MinHeapNode:

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

def printCodes(root, strr):
	if root == None:
		return
	if root.data is not '$':
		print(str(root.data) + ': ' + strr)
	printCodes(root.left, strr + '0')
	printCodes(root.right, strr + '1')

def storeCodes(root, strr):
	if root == None:
		return
	if root.data is not '$':
		codes[root.data] = strr
	storeCodes(root.left, strr + '0')
	storeCodes(root.right, strr + '1')

def huffmanCodes(s):
	global cnt
	for v in freq:
		heapq.heappush(minheap, (freq[v], freq[v] + cnt, MinHeapNode(v, freq[v])))
		cnt += 1
	while len(minheap) is not 1:
		left = minheap[0][2]
		heapq.heappop(minheap)
		right = minheap[0][2]
		heapq.heappop(minheap)
		top = MinHeapNode('$', left.freq + right.freq)
		top.left = left
		top.right = right
		heapq.heappush(minheap, (top.freq, top.freq + cnt, top))
		cnt += 1
	storeCodes(minheap[0][2], '')

def calcFreq(strr, n):
	for i in range(n):
		if strr[i] not in freq:
			freq[strr[i]] = 1
		else:
			freq[strr[i]] += 1
if __name__ == '__main__':
	t = int(input())
	while t > 0:
		strr = input()
		encodedString = ''
		decodedString = ''
		calcFreq(strr, len(strr))
		huffmanCodes(len(strr))
		for i in strr:
			encodedString += codes[i]
		decodedString = decodeHuffmanData(minheap[0][2], encodedString)
		print(decodedString)
		t = t - 1


def decodeHuffmanData(root, binaryString):
	i = 0
	tmp = root
	res = ''
	for digit in binaryString:
		if digit == '0':
			tmp = tmp.left
		else:
			tmp = tmp.right
		if tmp.data != '$':
			res += tmp.data
			tmp = root
	return res


def decodeHuffmanData(root, binaryString):
	n = len(binaryString)
	i = 0
	start = 0
	values = list(codes.values())
	output = ''
	d = {v: k for (k, v) in codes.items()}
	while i < n:
		if binaryString[start:start + i + 1] in d:
			output = output + d[binaryString[start:start + i + 1]]
			start = start + i + 1
			i = 0
		else:
			i = i + 1
	return output


def decodeHuffmanData(root, binaryString):
	newstring = ''
	newroot = root
	for i in binaryString:
		if i == '1':
			if newroot.right.data != '$':
				newstring = newstring + newroot.right.data
				newroot = root
			else:
				newroot = newroot.right
		elif newroot.left.data != '$':
			newstring = newstring + newroot.left.data
			newroot = root
		else:
			newroot = newroot.left
	return newstring


def decodeHuffmanData(root, binaryString):
	result = []
	i = 0
	current = root
	while i < len(binaryString):
		if binaryString[i] == '0':
			current = current.left
		else:
			current = current.right
		if not current.left and (not current.right):
			result.append(current.data)
			current = root
		i += 1
	return ''.join(result)


def decodeHuffmanData(root, binaryString):
	temp = root
	result = []
	for char in binaryString:
		if char is '0':
			temp = temp.left
		else:
			temp = temp.right
		if temp.left is None and temp.right is None:
			result.append(temp.data)
			temp = root
	return ''.join(result)


class TreeTraversal:

	def __init__(self):
		self.res = {}

	def traversetree(self, root, string=''):
		if root == None:
			return string
		if root.data != '$':
			self.res[string] = root.data
			return
		self.traversetree(root.left, string + '0')
		self.traversetree(root.right, string + '1')
		return

	def get_result(self):
		return self.res

def decodeHuffmanData(root, binaryString):
	obj = TreeTraversal()
	obj.traversetree(root)
	res = obj.get_result()
	char = ''
	output = ''
	for i in range(len(binaryString)):
		char = char + binaryString[i]
		if char in res:
			output += res[char]
			char = ''
	return output


def get_prefic_codes(root, str, codes):
	if root is None:
		return None
	left = get_prefic_codes(root.left, str + '0', codes)
	right = get_prefic_codes(root.right, str + '1', codes)
	if left is None and right is None and (root.data != '$'):
		codes[str] = root.data

def decodeHuffmanData(root, binaryString):
	codes = {}
	get_prefic_codes(root, '', codes)
	res = ''
	curr = ''
	for ele in binaryString:
		curr += ele
		if curr in codes:
			res += codes[curr]
			curr = ''
	return res


def inorder(root, d, path):
	if root.left is None and root.right is None:
		d[path] = root.data
		return
	inorder(root.left, d, path + '0')
	inorder(root.right, d, path + '1')

def decodeHuffmanData(root, s):
	d = {}
	inorder(root, d, '')
	l = 0
	r = 1
	n = len(s)
	ans = ''
	while r <= n:
		code = s[l:r]
		if code in d:
			ans += d[code]
			l = r
		r += 1
	return ans


def decodeHuffmanData(root, binaryString):

	def preorder(root, st):
		if root:
			if root.data != '$':
				dic[st] = root.data
				return
			preorder(root.left, st + '0')
			preorder(root.right, st + '1')
		return
	dic = {}
	preorder(root, '')
	s = ''
	res = ''
	for i in binaryString:
		s += i
		if dic.get(s):
			res += dic[s]
			s = ''
	return res


def decodeHuffmanData(root, binaryString):
	counter = {}
	traversal(root, '', counter)
	a = list(binaryString)
	temp = ''
	res = ''
	for i in range(len(a)):
		temp += a[i]
		if temp in counter:
			res += counter[temp]
			temp = ''
	return res

def traversal(root, ccode, counter):
	if root == None:
		return
	if root.left == None and root.right == None:
		counter[ccode] = root.data
		return
	traversal(root.left, ccode + '0', counter)
	traversal(root.right, ccode + '1', counter)


def decodeHuffmanData(root, s):
	l = []
	temp = root
	for i in s:
		if i == '0':
			temp = temp.left
		else:
			temp = temp.right
		if not temp.left and (not temp.right):
			l.append(temp.data)
			temp = root
	return ''.join(l)


def decodeHuffmanData(root, binaryString):
	c = root
	fstr = ''
	for i in binaryString:
		if i == '0':
			c = c.left
		elif i == '1':
			c = c.right
		if c.left is None and c.right is None:
			fstr += c.data
			c = root
	return fstr


def decodeHuffmanData(root, str1):
	ans = ''
	temp = root
	for i in str1:
		if i == '0':
			temp = temp.left
		elif i == '1':
			temp = temp.right
		if not temp.left and (not temp.right):
			ans += temp.data
			temp = root
	return ans


def decodeHuffmanData(root, str):
	ans = ''
	tmp = root
	for i in str:
		if i == '0':
			tmp = tmp.left
		elif i == '1':
			tmp = tmp.right
		if not tmp.left and (not tmp.right):
			ans += tmp.data
			tmp = root
	return ans


def decodeHuffmanData(root, binaryString):
	curr = root
	res = ''
	for i in range(len(binaryString)):
		if not curr.left and (not curr.right):
			res += curr.data
			curr = root
		if binaryString[i] == '0':
			curr = curr.left
		elif binaryString[i] == '1':
			curr = curr.right
	if not curr.left and (not curr.right):
		res += curr.data
	return res


def decodeHuffmanData(root, binaryString):
	cur = root
	ans = ''
	l = len(binaryString)
	for x in binaryString:
		if x == '0':
			cur = cur.left
		if x == '1':
			cur = cur.right
		if cur.left == None and cur.right == None:
			ans += cur.data
			cur = root
	return ans


def decodeHuffmanData(root, binaryString):
	trav = root
	output = ''
	for s in binaryString:
		if s == '0':
			trav = trav.left
		elif s == '1':
			trav = trav.right
		if trav.left is None and trav.right is None:
			output += trav.data
			trav = root
	return output


def decodeHuffmanData(root, binaryString):
	string = ''
	temp = []
	temp.append(root)
	for num in binaryString:
		if num == '0':
			root = root.left
		elif num == '1':
			root = root.right
		if root.data != '$':
			string = string + root.data
			root = temp[0]
	return string


def decodeHuffmanData(root, binaryString):
	i = 0
	dec_str = ''
	c = root
	for i in binaryString:
		if i == '0':
			c = c.left
		if i == '1':
			c = c.right
		if c.right == None and c.left == None:
			dec_str += c.data
			c = root
	return dec_str


def decodeHuffmanData(root, binaryString):
	temp = root
	result = []
	for c in binaryString:
		if c == '0':
			temp = temp.left
		else:
			temp = temp.right
		if temp.left == None and temp.right == None:
			result.append(temp.data)
			temp = root
	x = ''.join(result)
	return x


def decodeHuffmanData(root, binaryString):
	res = ''
	current = root
	for c in binaryString:
		if c == '0' and current.left:
			current = current.left
		elif c == '1' and current.right:
			current = current.right
		if not current.left and (not current.right):
			res += current.data
			current = root
	return res


def decodeHuffmanData(root, binaryString):
	if root is None or binaryString == '':
		return 0
	else:
		i = 0
		dec_str = ''
		curr = root
		for i in binaryString:
			if i == '0':
				curr = curr.left
			if i == '1':
				curr = curr.right
			if curr.right == None and curr.left == None:
				dec_str += curr.data
				curr = root
		return dec_str