// C++ version
string ss;
int idx;
int len;

void CheckNode(node * root) {
    
    if (root->data > 0) {
        std::cout << root->data;
        return;
    }
        
    if (ss[idx++] == '0') {
        CheckNode(root->left);
    }
    else {
        CheckNode(root->right);
    }
    
}

void decode_huff(node * root, string s) {
    if (root == nullptr)
        return;
    
    ss = s;
    len = ss.length();
    idx = 0;
    
    
    while (idx < len) {
        CheckNode(root);     
    }
    std::cout << '\n';
}

def decodeHuff(root, s):
    i = 0
    node = root
    res = ""
    while i < len(s):
        while node.data == chr(0):
            if s[i] == '0':
                assert node.left
                node = node.left
            else:
                assert node.right
                node = node.right
            i += 1
        res += node.data
        node = root
    print(res)

def decodeHuff(root, s):
	#Enter Your Code Here
    string = ""
    cur = root
    for si in s:
        if si == '0':
            cur = cur.left
        elif si == '1':
            cur = cur.right
        if cur.left is None and cur.right is None:
            string += cur.data
            cur = root
            
    print(string)