Diameter of tree

[1vf9z8AR]

Question-
https://www.hackerearth.com/practice/data-structures/trees/binary-and-nary-trees/tutorial/
at the bottom

My diameter is incorrect but close to actual diameter

  #include<iostream>
using namespace std;
struct node
{
    int val;
    node* left;
    node* right;
};
void insert(node* &newnode,int data)
{
    newnode=new node;
    newnode->val=data;
    newnode->left=NULL;
    newnode->right=NULL;
}
int diameter=0;
int dia(node* current,int ans)
{
    if(current)
    {
        //cout<<current->val<<endl;
        int ld=dia(current->left,ans+1);
        int rd=dia(current->right,ans+1);
        if(ld+rd+1>diameter)
            diameter=ld+rd+1;
        if(ld>rd)
            return ld;
        else
            return rd;
    }
    else
        return ans-1;
}
int main()
{
    node *root=NULL,**ptr;
    int no,x;
    cin>>no>>x;
    insert(root,x);
    for(int i=0;i<no-1;i++)
    {
        ptr=&root;
        string str;
        int temp;
        cin>>str;
        cin>>temp;
        for(int j=0;str[j]!='\0';j++)
        {
            if(str[j]=='L')
            {
                if((*ptr)->left==NULL)
                    insert((*ptr)->left,0);
                ptr=&((*ptr)->left);
            }
            else
            {
                if((*ptr)->right==NULL)
                    insert((*ptr)->right,0);
                ptr=&((*ptr)->right);    
            }
        }
        insert((*ptr),temp);
    }
    dia(root,0);
    cout<<diameter;
    return 0;
}

[dutch]

Didn't ne555 tell you how to do it in your previous post that you've apparently abandoned?

[salem c]

Get rid of the messy global variables.

int dia(node* current)
{
    if(current)
    {
        //!! diameter is whatever the sub-trees are, +1
        int ld=dia(current->left)+1;
        int rd=dia(current->right)+1;
        if(ld>rd)
            return ld;
        else
            return rd;
    }
    else
        return 0;  //!! empty tree is zero diameter
}

[dutch]

@salem c, It looks like he's building the tree incorrectly since he's "inserting" extra nodes.

[salem c]

@dutch, I was rather assuming a sane tree, oh well.

[1vf9z8AR]

Is the insertion correct now?

#include<iostream>
using namespace std;
struct node
{
    int val;
    struct node* left;
    struct node* right;
};
node* insert(int data)
{
    node* newnode=new node;
    newnode->val=data;
    newnode->left=NULL;
    newnode->right=NULL;
    return newnode;
}
int diameter=0;
int dia(node* current)
{
    if(current)
    {
        int ld=dia(current->left);
        int rd=dia(current->right);
        //cout<<current->val<<" "<<ld<<" "<<rd<<endl;
        if(ld+rd+1>diameter)
            diameter=ld+rd+1;
        if(ld>rd)
            return ld+1;
        else
            return rd+1;
    }
    else
        return 0;
}
int main()
{
    int no,x;
    cin>>no>>x;
    node *root,**ptr;
    root=insert(x);
    for(int i=0;i<no-1;i++)
    {
        ptr=&root;
        string str;
        int temp;
        cin>>str;
        cin>>temp;
        for(int j=0;str[j]!='\0';j++)
        {
            if(str[j]=='L')
            {
                if((*ptr)->left==NULL)
                    (*ptr)->left=insert(0);
                ptr=&((*ptr)->left);
            }
            else
            {
                if((*ptr)->right==NULL)
                    (*ptr)->right=insert(0);
                ptr=&((*ptr)->right);
            }
        }
        (*ptr)=insert(temp);
    }
    dia(root);
    cout<<diameter;
}

[ne555]

not quite
consider this input

3 42
LL
13
L
54

that sould give you 42 -> 54 -> 13 (all left children) but your code produces only 42 -> 54

at line 63 you are at the node described by the string, but instead of simply set its value you create a new node


again, create a function for printing the tree (I'll suggest preorder)

[1vf9z8AR]

ohhh Now I understand.

When I reached the last position, I created a 0 node at the position but also an extra node.

I replaced line 63 by
(*ptr)->val=temp;