linear algorithm on a binary three in-order-visit-like

Question

I have to write an algorithm in C that takes in input a Binary Search Tree. The exercise defines as "left visit" the visit that starts from the root of the sub tree and go left as long as possible. Similarly it defines the "right visit". The exercise ask to print the key of the three which has the left visit strictly bigger than the right visit. It also ask to print this key in ascending order,and the algorithm must works in linear time, so I have to implement an in-order-visit-like algorithm. Now, I have written an algorithm that works in linear time but in some case it didn't work as a in-order-visit and so the printed key aren't in ascending order, but I don't know how to manage to overtake this obstacles. How can I compare the left visit and the right without first of all implement a recursion on the left and on the right?

#include<stdio.h>
#include<stdlib.h>


typedef struct _node {
        int dato;
    struct _node *left;
        struct _node *right;
}node;


typedef struct _ret {
        int sin;
        int des;
        }res;


node *inserisci(node *root, int insert)
{
 if(root==NULL) {
        node * new=(node*)malloc(sizeof(node));
        new->left=NULL;
        new->right=NULL;
        new->dato=insert;
        return new;
}
 if(root->dato < insert) root->right =inserisci(root->right,insert);
 else root->left = inserisci(root->left,insert);
 return root;
}


res somma(node * u)
{
res ret; res ciao_sx; res ciao_dx;

if(u==NULL) return;

if(u->left==NULL && u->right==NULL)
        {
        ret.sin=0;
        ret.des=0;
        return ret;
        }

if(u->left!=NULL && u->right!=NULL)
        {
        ciao_sx=somma(u->left);
        ret.sin= ciao_sx.sin+1;
        ciao_dx=somma(u->right);
        ret.des= ciao_dx.des+1;

        if(ret.sin > ret.des )
                {
                printf("%d\n",u->dato);
                }
        return ret;
        }

if(u->left!=NULL && u->right==NULL)
        {
        ciao_sx=somma(u->left);
        ret.sin= ciao_sx.sin+1;
        ret.des= 0;
        printf("%d\n",u->dato);

        return ret;
        }

if(u->left==NULL && u->right !=NULL)
        {
        ciao_dx=somma(u->right);
        ret.des= ciao_dx.des +1;
        ret.sin=0;
        return ret;

        }
}





int main()
{
int n,i,x;
scanf("%d",&n);
node *root=NULL;
for(i=0;i<n;i++) {
        scanf("%d",&x);
        root=inserisci(root,x);
}

somma(root);

return 0;
}

I don't know how to post the code and the code that I've written works, there aren't bugs. Can you explain me how to post the code? Thanks! — Giovanni Mauro, Sep 13 '15 at 14:27
@GiovanniMauro Just copy and paste the code and then select the code using mouse and press ctrl-k. — Sumeet, Sep 13 '15 at 14:30
@GiovanniMauro In a binary search tree how can left visit be bigger than right visit? — Sumeet, Sep 13 '15 at 14:33
@Dante. the left visit are the number of key that starts from the root and go left as long as possible. Now I'm going to post an image that explain better than me — Giovanni Mauro, Sep 13 '15 at 14:38
I can't because I haven't enough reputation, here is the pic https://drive.google.com/file/d/0B8MvXbwdniwbRmNVdkNYbklzejQ/view?usp=sharing — Giovanni Mauro, Sep 13 '15 at 14:41
@GiovanniMauro I think you can go for tree traversal like inorder. — Sumeet, Sep 13 '15 at 14:58
@Dante. you have been very clear and I'm very grateful. I haven't thinked about the idea of adding a filed because I thought that the teacher said that we can't but he was referring about another exercise. I have only 1 question. Why have you added the field "visited" and then you have used it only in the function that insert the key into the tree? May I write the entire code without using this new field? Thanks — Giovanni Mauro, Sep 13 '15 at 17:30
@GiovanniMauro Yes definitely.I will update my answer,Thanks for reminding me. — Sumeet, Sep 13 '15 at 17:34
@GiovanniMauro I realized later that visited is not needed, so you can remove it. — Sumeet, Sep 13 '15 at 17:36
@Dante. Perfect, how can I rate you as better as possible? I'm not confident with this site, it's the second time I write :) — Giovanni Mauro, Sep 13 '15 at 18:31
@Dante. let me ask another question, the complexity of the compute_values is O(n) and the complexity of the iot is O(log n), right? — Giovanni Mauro, Sep 13 '15 at 20:31
@GiovanniMauro upvote means hitting the upward arrow,where a 0 is displayed above tick mark.If you hit the Downward arrow,it means you do not like the answer due to its incorrectness or other reasonable causes. — Sumeet, Sep 14 '15 at 07:22

Sumeet · Accepted Answer · 2015-09-13T17:35:09.287

This problem can be solved in linear time.

The trick is to compute the left visit and right visit values in BOTTOM-UP fashion so that we can do the following:

left_visit of node = left_visit of its left child + 1

and

right_visit of node = right_visit of its right child + 1

with the condition:

if(node is null)
 left_vist is 0 as well as right_visit is also 0.

Since we can easily very easily trace this path in bottom up fashion using an inorder traversal we will compute the values of left_visit and right_visit using that.

Main Idea

We know we can very easily write a recursive inorder traversal.

And we know that when we encounter a node which has no left child,we have reached the bottom,so this is where we start to compute the values using the rules as specified above.

The reason why this will work is because when the recursive call for the inorder traversal of a node's left child is complete,its left child will have its left_visit computed and all we have to do is add 1 to compute the current node's left_visit value and same logic applies for right vist.

Time Complexity is O(N) ,that is linear as inorder traversal is done in linear time.

Using the above algorithm,Here is the C code:

#include <stdio.h>
#include <stdlib.h>
typedef struct tree tree;
struct tree{
   int value;
   tree *left;
   tree *right;       
   int lv;
   int rv;
};
tree *insert(tree *ptr,int x)
{
    if(ptr==NULL)
    {
        ptr=(tree *)malloc(sizeof(tree));
        ptr->left=NULL;
        ptr->right=NULL;
        ptr->value=x;            
        return ptr;
    }
    else if(ptr->value>x)
        {ptr->left=insert(ptr->left,x);return ptr;}
    else { ptr->right=insert(ptr->right,x);return ptr;}
}
void compute_values(tree *ptr)
{
    if(ptr==NULL)
    return;
    compute_values(ptr->left);
    if(ptr->left==NULL)
     ptr->lv=0;
    else ptr->lv=ptr->left->lv+1;    
    compute_values(ptr->right);
    if(ptr->right==NULL)
     ptr->rv=0;
    else ptr->rv=ptr->right->rv+1;   
}
void iot(tree *ptr)
{
    if(ptr==NULL)
     return;
    iot(ptr->left);  
      if(ptr->lv > ptr->rv)
       printf("%d ",ptr->value);
    iot(ptr->right);
}
int main()
{
    tree *root=NULL;
    int i;
    /*insert 6  elements*/        
     root=insert(root,4);
     root=insert(root,5);
     root=insert(root,3);
     root=insert(root,1);
     root=insert(root,2);
     root=insert(root,0);
     root=insert(root,6);
     compute_values(root);/*compute the left and right visit.*/
     printf("the nodes which have left visit strictly > than right visit\n");
     iot(root);/*inorder traversal*/   
}

Just a small nit. Without arguments, `int main()` is properly `int main (void)`. Yes, I know you know, but when providing answers to others that may not, it is always best to be as syntactically correct as possible. (prevents passing on bad habits...) And since it is an `int foo (void)` it returns a value back to the shell (even if MS let's you get away without it). `return 0;` at the end. — David C. Rankin, Sep 13 '15 at 18:11
There may be one other little fix as well. `ptr = malloc (sizeof *ptr);` would be preferred. See: [**Do I cast the result of malloc?**](http://stackoverflow.com/q/605845/2173917) — David C. Rankin, Sep 13 '15 at 19:52

linear algorithm on a binary three in-order-visit-like

1 Answers1