void decode_huff(node * root, string s) {
    node* curr = root;
    string print;
    while(!s.empty())
    {
        if(curr->data != '\0')
        {
            print += curr->data;
            curr = root;
            continue;
        }
        if(s.front() == '0')
        {
            curr = curr->left;
        }
        else
        {
            curr = curr->right;
        }
        s.erase(0, 1);
    }
    print += curr->data;
    cout << print;
}

// 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)