Given the string input, how can we traverse the binary tree recursively

Let's say our binary tree (bt) looks like this:

Node* root = new Node();
  root->left = new Node("B");
  root->right = new Node();
  root->right->right = new Node("A");
  root->right->left = new Node();
  root->right->left->right = new Node("D");
  root->right->left->left = new Node("C");

and we are given the string "01111". This string should decode to "BAA".

I can't wrap my head around the "conditional" recursion. I am especially stuck on having the function to continue to process the string after the first "1". All my previous attempts would make the program end and only print "B A".

Here is working code that will get you the result "B A A", but I am convinced it can be written better, cleaner, and prettier.

void Decode(const string& unambiguous_message, const Node* root, const Node* current, size_t index = 0) {
    // Base case: if index reaches the end of the string, stop
    if (index >= unambiguous_message.length()) {
        return;
    }

    if (current->left == nullptr && current->right == nullptr) {
        cout << current->data << " ";
        Decode(unambiguous_message, root, root, index); // Restart from root
    }

    // Process the current character
    if (unambiguous_message[index] == '0' && current->left != nullptr) {
        Decode(unambiguous_message, root, current->left, index + 1);
    } else if (unambiguous_message[index] == '1' && current->right != nullptr) {
        Decode(unambiguous_message, root, current->right, index + 1);
    } else {
        // Invalid path: restart from root at next index to try next prefix
        Decode(unambiguous_message, root, root, index + 1);
    }
}

Also, if there is a better way to translate the bt from the image to code.

I am expecting the string to be processed completely. I just cannot figure out a better, cleaner or smarter way to handle these types of choice/conditional recursions.

I see two questions here:

1. How to have a recursive function continue in order to process the remaining string after the first output is generated?

   Although you have provided code that does this in a certain way, that is not the way to approach it. You'd better unwind from recursion before decoding for the next output.

2. How to build a tree without having to code as many new Node() assignments as there are nodes in the tree?

But first:

The Node class

This is about Huffman encoding/decoding. As your tree would be a full binary tree, where its leaves have character data, I would:

• include a constructor that takes left and right as arguments, with the goal to set the instance members directly during construction, and not later.
• make members immutable, to bring the first point home.
• enforce that the tree is a full binary tree, i.e. no node should have just one child.
• set the type of the data member to char and not string: you'd only store single characters there.

The Node class could then be like this:

class Node {
private:
    const char data = '.';
    const Node *left = nullptr;
    const Node *right = nullptr;
    
public:
    Node() {}
    Node(char data) : data(data) {}
    Node(Node* left, Node* right) : left(left), right(right) {
        if (!left || !right) { // Apply full binary tree constraint
            std::cout << "Node constructor arguments should be non-null\n";
            exit(1);
        }
    }
    
    bool is_leaf() const {
        return !left && !right;
    }
}

The first question: unwinding from recursion

I can't wrap my head around the "conditional" recursion. I am especially stuck on having the function to continue to process the string after the first "1".

A recursive approach can be fine, even though it is a case of tail recursion and would be suitable for a plain loop. But to continue deepening the recursion at each input character, as done by the code you shared, is a stretch. A logical state where you would exit the recursion tree is where you retrieve a decoded character from a leaf of the binary tree. At that point completely unwind from recursion. That way the recursion depth will never be more than the height of your binary tree: it will invariably match the depth of the current node in the binary tree.

So you would restart the recursion from scratch when starting the decoding for a new output. To achieve this, make the recursive function such that it only deals with generating one output character. Leave it for the caller to initiate the next call from the top.

Also, I would build a string and not use cout in your function. Leave that to the caller of the function, or whatever else they want to do with the decoded string that the function can return.

Here is a method you could have on the Node class, which uses recursion to decode characters for just one output, by traversing the binary tree from the root to one of its leaves. It takes a character pointer which it updates so that after a call of this function, a next call will continue from where it stopped:

    std::string decode_one(char* &chr_ptr) const {
        return is_leaf() ? data
            : !*chr_ptr ? "" // message is not a valid encoding
            : (*chr_ptr == '0' ? left : right)->decode_one(++chr_ptr); // Recur
    }

Use this method in another method that decodes a whole string:

    std::string decode(std::string unambiguous_message) const {
        char* chr_ptr = unambiguous_message.data();
        std::string decoded = "";
        while (*chr_ptr) decoded += decode_one(chr_ptr);
        return decoded;
    }

Now you can call it as a method:

    std::cout << root->decode("01111");

The second question: building the tree

is [there] a better way to translate the bt from the image to code.

I take this as a question for a more generic approach that does not need one line of new Node() code for each node of your tree. One idea is to create a function that takes as input some encoding for the desired tree, like a pre-order sequence for it.

    static Node *from_pre_order(char* &chr_ptr) {
        char ch = *chr_ptr;
        if (!ch) {
            std::cout << "Unexpected end of pre-order input\n";
            exit(1);
        }
        if (ch != '.') return new Node(ch);
        Node* save_left = from_pre_order(++chr_ptr);
        return new Node(save_left, from_pre_order(++chr_ptr));
    }

To facilitate calling this function with a string argument, add this wrapper:

    static Node *from_pre_order(std::string pre_order) {
        char* chr_ptr = pre_order.data();
        return from_pre_order(chr_ptr);
    }

The example tree you used could now be created as follows:

    Node *root = Node::from_pre_order(".B..CDA");

NB: In practice you would build a tree based on some message that needs encoding, using the Huffman encoding algorithm.

Result

Here is all of the above put together with an example call:

#include <iostream>
#include <vector>

class Node {
private:
    const char data = '.';
    const Node *left = nullptr;
    const Node *right = nullptr;
    
public:
    Node() {}
    Node(char data) : data(data) {}
    Node(Node* left, Node* right) : left(left), right(right) {
        if (!left || !right) { // Apply full binary tree constraint
            std::cout << "Node constructor arguments should be non-null\n";
            exit(1);
        }
    }
    
    bool is_leaf() const {
        return !left && !right;
    }
    
    char decode_one(char* &chr_ptr) const {
        return is_leaf() ? data
            : !*chr_ptr ? '\0' // message is not a valid encoding
            : (*chr_ptr == '0' ? left : right)->decode_one(++chr_ptr); // Recur
    }
    
    std::string decode(std::string unambiguous_message) const {
        char* chr_ptr = unambiguous_message.data();
        std::string decoded = "";
        while (*chr_ptr) decoded += decode_one(chr_ptr);
        return decoded;
    }
    
    static Node *from_pre_order(char* &chr_ptr) {
        char ch = *chr_ptr;
        if (!ch) {
            std::cout << "Unexpected end of pre-order input\n";
            exit(1);
        }
        if (ch != '.') return new Node(ch);
        Node* save_left = from_pre_order(++chr_ptr);
        return new Node(save_left, from_pre_order(++chr_ptr));
    }

    static Node *from_pre_order(std::string pre_order) {
        char* chr_ptr = pre_order.data();
        return from_pre_order(chr_ptr);
    }
};

int main() {
    Node *root = Node::from_pre_order(".B..CDA");
    std::cout << root->decode("01111") << "\n";
    return 0;
}