Helo with building binary trees using pointers

Hi to everyone. I'm currently working on a school homework using binary trees. I feel as though I'm almost finished, but I have a problem I couldn't figure out to solve.

Although I have a general idea of how structures and pointers work, I still get confused with their usage. I've been searching the internet for a comprehensive explanation of how they work but most of what I've found lack the details that I need to know. So I came here hoping someone can explain these things better. Forgive me 'coz I really have a poor comprehension when it comes to pointers.

My algorithm constructs a binary tree given the preorder and inorder sequence (in the form of strings).

So I have a global structure declared this way:

Code:

struct Node{
 
  char letter;
  struct Node *left;
  struct Node *right;  
      
};

and a global pointer to the root.

Code:

struct Node *root;

this is the rest of the code:

Code:

int main(){
  
  char preorder[5]="RASIN"; preorder[5]='\0';
  char inorder[5]="SAIRN"; inorder[5]='\0';

  root=malloc(sizeof(struct Node));
  *root=buildTree(preorder, inorder); //this line starts the construction of the tree from the root to its branches
  
  getch();
}

struct Node buildTree(char *preorder, char *inorder){ //I'm using a recursive method to build the tree. This is how I visualize the algorithm:
     
     struct Node *newNode=malloc(sizeof(struct Node));
     
     if(strlen(inorder)==1){
         newNode->left=NULL;
         newNode->right=NULL;
         newNode->letter=inorder[0];
         return *newNode;
     }
       
     int index = findLetterToPut(preorder, inorder);
     *newNode->left = buildTree(preorder, substr(inorder, 0, index));
     *newNode->right = buildTree(preorder, substr(inorder, index+1, strlen(inorder)-1));
     
     newNode->letter = inorder[index];
     
     
     return *newNode;
     
}

this is the function findLetterToPut(...):

Code:

int findLetterToPut(char *preorder, char *inorder){
     
     int index1, index2;
     
     for(index1=0; index1<strlen(preorder); index1++){
                  
        for(index2=0; index2<strlen(inorder); index2++){
            
            if(preorder[index1]==inorder[index2] )
                return index2;
                
        }
        
     }
}

The program works properly if I remove this line from the buildTree function:

Code:

*newNode->right = buildTree(preorder, substr(inorder, index+1, strlen(inorder)-1));

However, only the left nodes are constructed without that line. The good thing is that these nodes are constructed properly. All pointers to the right node (starting from the root)are therefore NULL without this line.

My question is: what's the problem with that line? If I include that line, an execution error occurs, e.g., illegal operation. That line is essential for constructing the right nodes.

Thanks for your time.

Lose the stars before newnode->

Thanks, but I still get the same errors. It must be my algorithm. this is my current buildTree function:

Code:

struct Node buildTree(char *preorder, char *inorder){
     
     struct Node newNode; 
     
     if(strlen(inorder)<=1){
         newNode.letter=inorder[0];
         return newNode;
     }
       
     int index = findLetterToPut(preorder, inorder);
 
    *newNode.left = buildTree(preorder, substr(inorder, 0, index));
    *newNode.right= buildTree(preorder, substr(inorder, index+1, strlen(inorder)-1));
     newNode.letter = inorder[index];

     return newNode;
     
}

Originally Posted by croman

Although I have a general idea of how structures and pointers work, I still get confused with their usage. I've been searching the internet for a comprehensive explanation of how they work but most of what I've found lack the details that I need to know. So I came here hoping someone can explain these things better. Forgive me 'coz I really have a poor comprehension when it comes to pointers.

Point at a poster on your wall. Ponder the difference between your hand (the pointer) and the poster (the thing pointed to). Ponder the similarities between them (this won't take long because there aren't any). And that's pointers.

Originally Posted by croman

this is the rest of the code:

Code:

int main(){
  
  char preorder[5]="RASIN"; preorder[5]='\0';
  char inorder[5]="SAIRN"; inorder[5]='\0';

I hope you weren't expecting all those letters in your final program. Hint: putting a six-character string into a five-character array may lead you to wonder where your last letter went. Bonus hint: preorder[5] doesn't exist, despite your attempts to assign to it.

Originally Posted by croman

Code:

struct Node buildTree(char *preorder, char *inorder){ //I'm using a recursive method to build the tree. This is how I visualize the algorithm:
     
     struct Node *newNode=malloc(sizeof(struct Node));
     
     if(strlen(inorder)==1){
         newNode->left=NULL;
         newNode->right=NULL;
         newNode->letter=inorder[0];
         return *newNode;
     }
       
     int index = findLetterToPut(preorder, inorder);
     *newNode->left = buildTree(preorder, substr(inorder, 0, index));
     *newNode->right = buildTree(preorder, substr(inorder, index+1, strlen(inorder)-1));
     
     newNode->letter = inorder[index];

I am surprised and alarmed that even part of this code works. You need to store pointers to the nodes, not try to write into the memory pointed to by newNode->left, because currently newNode->left (and newNode->right, for that matter) point to somewhere in eastern New Jersey, and unless you also happen to be in eastern New Jersey this could be problematic. Instead you want your buildTree function to return the address of (i.e., the pointer to) the data, and store those addresses in your node.

Originally Posted by croman

Thanks, but I still get the same errors. It must be my algorithm. this is my current buildTree function:

Code:

struct Node buildTree(char *preorder, char *inorder){
     
     struct Node newNode; 
     
     if(strlen(inorder)<=1){
         newNode.letter=inorder[0];
         return newNode;
     }
       
     int index = findLetterToPut(preorder, inorder);
 
    *newNode.left = buildTree(preorder, substr(inorder, 0, index));
    *newNode.right= buildTree(preorder, substr(inorder, index+1, strlen(inorder)-1));
     newNode.letter = inorder[index];

     return newNode;
     
}

I agree with tabstop, this should not work at all, but I'm also wondering what part of "lose the star before newnode" you didn't understand...

thanks for the observations tabstop and CommonTater.

Point at a poster on your wall. Ponder the difference between your hand (the pointer) and the poster (the thing pointed to). Ponder the similarities between them (this won't take long because there aren't any). And that's pointers.

I apologize for my ignorance on this thing. Haha. Thanks for pointing that out. I know exactly the difference between the pointer and the address (assuming what I know is right -- well maybe not). It just really sucks I can't get them right in the implementation.

I hope you weren't expecting all those letters in your final program. Hint: putting a six-character string into a five-character array may lead you to wonder where your last letter went. Bonus hint: preorder[5] doesn't exist, despite your attempts to assign to it.

This was more a code that I arrived at out of trial and error (i.e, without understanding the background behind this). My problem was that when I print the preorder string in the buildTree function without the statement preorder[5]='\0'; I get an output of the exact string with a concatenation of 2 garbage values at its end. So I thought of terminating it. And it worked ("worked" in the sense that when I printed it again using printf, there were no longer garbage values at its end). So yeah, something must be really wrong with my code.

I am surprised and alarmed that even part of this code works. You need to store pointers to the nodes, not try to write into the memory pointed to by newNode->left, because currently newNode->left (and newNode->right, for that matter) point to somewhere in eastern New Jersey, and unless you also happen to be in eastern New Jersey this could be problematic. Instead you want your buildTree function to return the address of (i.e., the pointer to) the data, and store those addresses in your node.

Thanks. It's a shame, really. It's a shame that I don't get the whole pointer-address implementation thing. What I wanted this function to do was to create a node and return that node to the calling function. In this statement:

Code:

*newNode->left = buildTree(preorder, substr(inorder, 0, index));

I wanted the newNode to point to another node (which will be generated by the called function). I'm just not sure if I did it right.


Or should it be more like this?

Code:

struct Node newNode; 

*newNode.left = buildTree(preorder, substr(inorder, 0, index));

I agree with tabstop, this should not work at all, but I'm also wondering what part of "lose the star before newnode" you didn't understand...

I tried removing the stars before it but it still didn't work. So I did a workaround that I thought was parallel to the idea that you were raising. But then I guess, I didn't really get it.

Originally Posted by croman

thanks for the observations tabstop and CommonTater.
\This was more a code that I arrived at out of trial and error (i.e, without understanding the background behind this). My problem was that when I print the preorder string in the buildTree function without the statement preorder[5]='\0'; I get an output of the exact string with a concatenation of 2 garbage values at its end. So I thought of terminating it. And it worked ("worked" in the sense that when I printed it again using printf, there were no longer garbage values at its end). So yeah, something must be really wrong with my code.

What it is, is that you need to count.

Code:

preorder[6] = "AINRS";

Code:

*newNode->left = buildTree(preorder, substr(inorder, 0, index));

I wanted the newNode to point to another node (which will be generated by the called function). I'm just not sure if I did it right.

So if you want to know what it does, maybe you should read the code. newNode->left is a pointer, as per your struct. * means "follow the address and get the data there". Therefore "*newNode->left" means "look at newNode->left, which gives you an address, and go to that address and put the data there". If you want to change the pointer, you need to change the pointer; the pointer is "newNode->left", so that's what you need to have on the left side of the equal sign.

Originally Posted by tabstop

What it is, is that you need to count.

Code:

preorder[6] = "AINRS";

So if you want to know what it does, maybe you should read the code. newNode->left is a pointer, as per your struct. * means "follow the address and get the data there". Therefore "*newNode->left" means "look at newNode->left, which gives you an address, and go to that address and put the data there". If you want to change the pointer, you need to change the pointer; the pointer is "newNode->left", so that's what you need to have on the left side of the equal sign.

Thanks mate! I just solved the problem! Your ideas helped a lot. This is now the new code:

Code:

int main(){
    
  char preorder[6]="RASIN"; 
  char inorder[6]="AINRS";
  
  
  root=malloc(sizeof(struct Node));
  root=buildTree(preorder, inorder);
  
}

Code:

struct Node *buildTree(char *preorder, char *inorder){
     
     struct Node *newNode=malloc(sizeof(struct Node));
     
     if(strlen(inorder)<=1){
         newNode->letter=inorder[0];
         
         return newNode;
     }
       
     int index = findLetterToPut(preorder, inorder);
 
     newNode->left = buildTree(preorder, substr(inorder, 0, index));
     newNode->right= buildTree(preorder, substr(inorder, index+1, strlen(inorder)-1));
     newNode->letter = inorder[index];
     
     
     return newNode;
     
     
}

It's working well. But I wonder if there are still flaws here.

You're allocating the root node twice. You don't have to allocate the root node explicitly, since buildTree does it for you.

Originally Posted by Fader_Berg

You're allocating the root node twice. You don't have to allocate the root node explicitly, since buildTree does it for you.

Thanks for pointing that out.