My binary tree creation code not printing any values

Question

I wrote this binary tree code to construct a tree and then print it:

#include <iostream>
#include<bits/stdc++.h>

using namespace std;

struct node
{
    int data;
    node* r;
    node* l;
    node(int data):data(data){};
};

void add(node*&root,vector<int>value,vector<char>direction)
{
    assert(value.size()==direction.size());
    node*curr=root;
    for(int i=0;i<(int)value.size();i++)
    {
        if(direction[i]=='R')
        {
            if(curr->r)
                assert(curr->r->data==value[i]);
            else
            {
                node*n=new node(value[i]);
                curr->r=n;
                curr=curr->r;
            }
        }
        else if(direction[i]=='L')
        {
            if(curr->l)
                assert(curr->l->data==value[i]);
            else
            {
                node*n=new node(value[i]);
                curr->l=n;
                curr=curr->l;
            }
        }
    }
}

void print_inorder(node*curr)
{
    if(!curr)
        return;
    print_inorder(curr->l);
    cout<<curr->data<<" ";
    print_inorder(curr->r);
}

int main()
{
    node* root=new node(1);
    add(root,{2,5},{'L','R'});
    add(root,{2,4,6},{'L','L','L'});
    add(root,{3,7},{'R','R'});
    print_inorder(root);
    return 0;
}

• the add function should construct the tree.
• the print function should print the tree inorder.

But it doesn't print any values when I run the code. I couldn't find the problem... What is my mistake?

Answer 1

There are these issues:

• The l and r fields are not initialised when allocating a new node. So this leads to undefined behaviour.

• In add, when a child node already exists, you still need to move to it, like you do in the else case.

Other remarks:

• What's the problem with "using namespace std;"?
• Why should I not #include <bits/stdc++.h>?

Here is the corrected code:

#include <iostream>
// Include standard headers, not <bits/stdc++.h>
#include <vector>
#include <cassert>

// Don't do: using namespace std;

struct node
{
    int data;
    node* r = nullptr; // Initialize!
    node* l = nullptr;
    node(int data) : data(data) {};
};

void add(node* &root, std::vector<int> value, std::vector<char> direction)
{
    assert(value.size() == direction.size());
    node* curr = root;
    for (int i = 0; i < (int)value.size(); i++)
    {
        if (direction[i] == 'R')
        {
            if (curr->r)
                 assert(curr->r->data == value[i]);
            else
                curr->r = new node(value[i]);
            curr = curr->r; // Always do this
        }
        else if (direction[i] == 'L')
        {
            if (curr->l)
                 assert(curr->l->data == value[i]);
            else
                curr->l = new node(value[i]);
            curr = curr->l; // Always do this
        }
    }
}

void print_inorder(node *curr)
{
    if (!curr)
        return;
    print_inorder(curr->l);
    std::cout << curr->data << " ";
    print_inorder(curr->r);
}

int main()
{
    node* root = new node(1);
    add(root, {2, 5}, {'L', 'R'});
    add(root, {2, 4, 6}, {'L', 'L', 'L'});
    add(root, {3, 7}, {'R', 'R'});
    print_inorder(root);
    return 0;
}