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)