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

Question

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

Photo representation

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.

• Alan Birtles: I don't think recursion is helping here, you just need two loops
• Pepijn Kramer: So you're basically implementing huffman decoding. They key issue is that whenever you reached a leaf node you should reset the algorithm to jump back to the root node. Recursion is not needed at all (@AlanBirtles I agree with you) but it might be part of your excercise. Example here : onlinegdb.com/MHqDqO9I6
• Jarod42: As you have working code, codereview.stackexchange.com seems more appropriate.
• Toby Speight: If you believe that the code works correctly, consider presenting your work (with its unit tests if you can) in a more-complete fashion over at Code Review. You'll likely get some suggestions on making it more efficient, easier to read, and better tested. Before you do that, make sure to read A guide to Code Review for Stack Overflow users first, as some things are done differently over there - e.g. question titles should simply say what the code does, as the question is always, "How can I improve this?".
• Swift - Friday Pie: Is recursion required? You can do this in a single loop and shortcut. In that case there is no problem to jump back to root.Recursive implementation would require more opaque implementation for tree's interface than this, not a node pointer.

Answer 1

I don't think the recursive function is helping.

All you need is a single loop through the characters of the string, interpreting each one, either as a character, or as a movement down the tree. After each complete character, reset to the root node

For example:

#include <iostream>
#include <string>
class Node {
 public:
 Node(char character) : character(character) {}
 //Make sure these nodes don't go out of scope, this class doesn't protect them
 Node(const Node* left, const Node* right) : left(left), right(right) {}
 char character;
 const Node* left= nullptr;
 const Node* right=nullptr;
 bool is_leaf_node() const { return left == nullptr && right == nullptr;}
};
int decode(const std::string& unambiguous_message, const Node* root_node) {
 auto iter = unambiguous_message.begin();
 while (iter < unambiguous_message.end()) {
 const Node* current_node = root_node;
 while (!current_node->is_leaf_node()) {
 
 if (iter == unambiguous_message.end())
 // incomplete message
 return -1;
 else if (*iter == '0')
 current_node = current_node->left;
 else if (*iter == '1')
 current_node = current_node->right;
 else
 //non-binary character
 return -1;
 iter = std::next(iter);
 
 }
 std::cout << current_node->character;
 }
 return 0;
}
int main() { 
 Node a('A');
 Node b('B');
 Node c('C');
 Node d('D');
 Node z(&c,&d);
 Node y(&z, &a);
 Node root(&b, &y);
 return decode("01111", &root);
 
}

This doesn't use a recursive call, but just uses one loop through the characters of the string.

Answer 2

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;
}