C Creating a binary tree based on a sequence

Question

I need help adjusting the createTree function.

Which accepts a string and after that character by character traverses it, creating a binary tree based on it

If it encounters the character 0, it recursively creates two sub-branches. If it encounters another character, it saves it in the leaf node.

For the string in the example, I need to make a tree as in the picture, but the function does not work properly for me. Thank you in advance for your advice.

    int x = 0;

    Node* createTree(string str, int si, int ei)
{
    if (si > ei)
        return NULL;

    Node *root = new Node((str[si] - '0'));

    if(str[si] != '0')
    {
        x++;
        root->m_Data = (str[si] - '0');
        return root;    
    }

    if(str[si]=='0')
    {
        x++;
        root->m_Left = createTree(str,x,ei);
        root->m_Right = createTree(str,x,ei);
    }

    return root;
}



int main ()
{
    
    string str = "050067089";
    
    Node *node = createTree(str,0,str.length());
    printPreorder(node);
    return 0;
}

Answer 1

The problem can quite easily be broken down into small steps (what you partly did in your question).

1. Start iterating at the first character
2. Create the root node
3. If the current character is non-zero, set the value of this node to this character
4. If current character is a zero, set this node to zero, create a left and a right node and get back to step 3 for every one of them. (That's the recursive part.)

Below is my implementation of this algorithm.

First, a little bit of setting up:

#include <iostream>
#include <string>
#include <memory>

struct Node;

// Iterator to a constant character, NOT a constant iterator
using StrConstIt = std::string::const_iterator;
using UniqueNode = std::unique_ptr<Node>;

struct Node
{
    int value;
    UniqueNode p_left;
    UniqueNode p_right;

    Node(int value)
        : value(value) {}
    
    Node(int value, UniqueNode p_left, UniqueNode p_right)
        : value(value), p_left(std::move(p_left)), p_right(std::move(p_right)) {}
};

As you can see, I'm using std::unique_ptr for managing memory. This way, you don't have to worry about manually deallocating memory. Using smart pointers is often considered the more "modern" approach, and they should virtually always be preferred over raw pointers.

UniqueNode p_createNodeAndUpdateIterator(StrConstIt& it, StrConstIt stringEnd)
{
    if (it >= stringEnd)
        return nullptr;

    UniqueNode node;

    if (*it == '0')
        // Create node with appropriate value
        // Create branches and increment iterator
        node = std::make_unique<Node>(
            0,
            p_createNodeAndUpdateIterator(++it, stringEnd),
            p_createNodeAndUpdateIterator(it, stringEnd)
        );
    else
    {
        // Create leaf node with appropriate value
        node = std::make_unique<Node>(*it - '0');
        // Increment iterator
        ++it;
    }

    return node;
}

UniqueNode p_createTree(StrConstIt begin, StrConstIt end)
{
    return p_createNodeAndUpdateIterator(begin, end);
}

The first function takes a reference to the iterator to the next character it should process. That is because you can't know how much characters a branch will have in its leaf nodes beforehand. Therefore, as the function's name suggests, it will update the iterator with the processing of each character.

I'm using iterators instead of a string and indices. They are clearer and easier to work with in my opinion — changing it back should be fairly easy anyway.

The second function is basically syntactic sugar: it is just there so that you don't have to pass an lvalue as the first argument.

You can then just call p_createTree with:

int main()
{
    std::string str = "050067089";
    UniqueNode p_root = p_createTree(str.begin(), str.end());

    return 0;
}

I also wrote a function to print out the tree's nodes for debugging:

void printTree(const UniqueNode& p_root, int indentation = 0)
{
    // Print the value of the node
    for (int i(0); i < indentation; ++i)
        std::cout << "| ";
    std::cout << p_root->value << '\n';

    // Do nothing more in case of a leaf node
    if (!p_root->p_left.get() && !p_root->p_right.get())
        ;
    // Otherwise, print a blank line for empty children
    else
    {
        if (p_root->p_left.get())                         
            printTree(p_root->p_left, indentation + 1);
        else
            std::cout << '\n';
        if (p_root->p_right.get())
            printTree(p_root->p_right, indentation + 1);
        else
            std::cout << '\n';
    }
}

Answer 2

Assuming that the code which is not included in your question is correct, there is only one issue that could pose a problem if more than one tree is built. The problem is that x is a global variable which your functions change as a side-effect. But if that x is not reset before creating another tree, things will go wrong.

It is better to make x a local variable, and pass it by reference.

A minor thing: don't use NULL but nullptr.

Below your code with that change and the class definition included. I also include a printSideways function, which makes it easier to see that the tree has the expected shape:

#include <iostream>

using namespace std;

class Node {
public:
    int m_Data;
    Node* m_Left = nullptr;
    Node* m_Right = nullptr;

    Node(int v) : m_Data(v) {}
};

// Instead of si, accept x by reference:
Node* createTree(string str, int &x, int ei)
{
    if (x >= ei)
        return nullptr;

    Node *root = new Node((str[x] - '0'));

    if(str[x] != '0')
    {
        root->m_Data = (str[x] - '0');
        x++; 
        return root;
    }

    if(str[x]=='0')
    {
        x++;
        root->m_Left = createTree(str,x,ei);
        root->m_Right = createTree(str,x,ei);
    }

    return root;
}

// Overload with a wrapper that defines x
Node* createTree(string str)
{
    int x = 0;
    return createTree(str, x, str.length());
}

// Utility function to visualise the tree with the root at the left
void printSideways(Node *node, string tab) {
    if (node == nullptr) return;
    printSideways(node->m_Right, tab + "  ");
    cout << tab << node->m_Data << "\n";
    printSideways(node->m_Left, tab + "  ");
}

// Wrapper for above function
void printSideways(Node *node) {
    printSideways(node, "");
}


int main ()
{    
    string str = "050067089";
    
    Node *node = createTree(str);
    printSideways(node);
    return 0;
}

So, as you see, nothing much was altered. Just si was replaced with x, which is passed around by reference, and x is defined locally in a wrapper function.

Here is the output:

      9
    0
      8
  0
      7
    0
      6
0
  5