My first post on this forum, long time lurker though. I'm running into a problem trying to search through an N-ary tree. I'm tasked with having the user input pairs of job titles and from there putting them into an N-ary tree, with the higher job titles at higher levels. I'm trying to write a function that will take the root and the desired job title and search through the tree and return where it's found so that I can insert the second job title under it. "parentnode" is the node in the tree where the first title entered can be found.

The function works good if I'm only dealing with one level (Ex. Input of President and Vice_President_1, and then President and Vice_President_2) but as soon as I try and put something under the second level, I get a segmentation fault. (Ex. Vice_President_1 and Sub_Manager_1). I believe it has to do with me trying to call the function recursively.

Here's the structure I'm working with:

struct node
	char title[TITLE];
	struct node * neighbors; //This is the head of the LL that is the neighbors
	struct node * firstsubnode;

Here's the function:

struct node *searchtree(struct node * root, char *title1)
	struct node *parentnode,*sublevel, *local;
	int found=0;
	printf("\nInside searchtree");
	for(sublevel = root; ((sublevel != NULL)&&(found==0)); sublevel = sublevel->neighbors)
		if(strcmp(sublevel->title, title1)==0) //Match detected
			printf("\nMatch detected!");
			parentnode = sublevel;
			found = 1;
			printf("\nReturning parentnode");
		else if((sublevel->firstsubnode != NULL)&&(found==0)) //Go down one level
			parentnode = searchtree(sublevel->firstsubnode, title1); //Recursively call this function to search through all the layers

first thing i notice is tree data structure is not correct
and recursion here wont work as there is some fundamental mistakes.

data structure should be something like following

struct node
	char title[TITLE];
        struct node *parent;
	struct node * firstchild; //This is the head of the LL that is the neighbors
	struct node * childrenlist; // this is the list of all children, starting from 1st child
        struct node * next;

now here is the sudo code of recursion:

struct node *searchtree(struct node * parent, char *title1)
     if(parent is NULL)
         return NULL;
     if(parent title match title1) //wohoo we found it
         return parent;

     for(every children of this parent) // this is the tricky loop for the parent, try it first..
          if( searchtree(child, title1 ) )
               return child; // this will be parent of your new child which you want to insert;

call it from main

parent = searchtree(root, title1);
if(parent is null)
    //oppps we didnt find parent
   //insert the child, again this is little bit tricky, as you have to insert it as firstchild is it is the firstchild, or in the children list of this parent

i hope this was helpful

This article has been dead for over six months. Start a new discussion instead.