Wsrtjtyk

I am writing a part of a program in which it traverses a binary tree until it finds the intended item in the tree (assuming that the item we are looking for always exists in the tree). The method I have adopted for searching in a tree is preorder tree walk.

Each node contains either a question or a statement. If the node is statement, it has no children. However, if the node is a question, it has exactly two children. In the follow you can see the header file for creating a node.

// two type of branch in the tree

enum response{

    YES,

    NO

};



// content of a node

union objInfoOrQInfo {

    char * object;

    char * question;

};



struct node{

    union objInfoOrQInfo container;

   // enum response existLeftChild;

   // enum response existRightChild;

    struct node * rightChild;

    struct node * leftChild;

};



void nodePrint(char * string); 

In the following code, I have populated a tree and implemented the pre-order tree walk

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include "node.h"



struct node * traverse(struct node * searchingNode, char * searchContent);





void nodePrint(char * string)

{

    struct node root;

    struct node left;

    struct node right;

    //second level

    struct node leftLeft;

    struct node leftRight;

    struct node rightLeft;

    struct node rightRight;



    // Populating the tree

    root.container.question = "Does it have a tail?";

    root.leftChild = &left;

    root.rightChild = &right;



    left.container.question = "Does it like a chase mice?";

    left.leftChild = &leftLeft;

    left.leftChild = &leftRight;

    right.container.question = "Is it flat, round and edible?";

    right.leftChild = &rightLeft;

    right.rightChild = &rightRight;



    leftLeft.container.object = "A Cat";

    leftLeft.leftChild = NULL;

    leftLeft.rightChild = NULL;

    leftRight.container.object = "A Pangolin";

    leftRight.leftChild = NULL;

    leftRight.rightChild = NULL;

    rightLeft.container.object = "A Pizza";

    rightLeft.leftChild = NULL;

    rightLeft.rightChild = NULL;

    rightRight.container.object = "Pete";

    rightLeft.leftChild = NULL;

    rightLeft.rightChild = NULL;





    // It   needs to traverse from the root until it finds the content you are asking for

    struct node * result = traverse(&root, string);

    if(result->leftChild != NULL || result->rightChild != NULL)

    {

        printf("Object: %sn","[NOTHING]");

        printf("Question: %sn",result->container.question);

        if(result->leftChild->container.object == NULL)

            printf("Yes: %sn",result->leftChild->container.question);

        else

            printf("Yes: %sn",result->leftChild->container.object);



        if(result->leftChild->container.object == NULL)

            printf("Yes: %sn",result->rightChild->container.question);

        else

            printf("Yes: %sn",result->rightChild->container.object);

    }

    else

    {

        printf("Object: %sn","[NOTHING]");

        printf("Question: %sn",result->container.question);

    }





}



// This function traverse from the root until it finds the desired content (return 1), otherwise (return -1)

struct node * traverse(struct node * searchingNode, char * searchContent) {



    // If the node is found, just return it.

    if (strcmp(searchingNode->container.question, searchContent) == 0)

        return searchingNode;



    // If the node is not found and we are at a leaf, return NIL

    if (searchingNode->leftChild == NULL && searchingNode->rightChild == NULL)

        return NULL;



    // Searching in the left and right subtrees, respectively.

    struct node *leftSubTree = traverse(searchingNode->leftChild, searchContent);

    struct node *rightSubTree;

    if(leftSubTree == NULL)

        rightSubTree = traverse(searchingNode->rightChild, searchContent);



    // Calculating the final result

    if (leftSubTree == NULL && rightSubTree == NULL)

        return NULL;

    else if (leftSubTree == NULL)

        return rightSubTree;

    return leftSubTree;

}

In order to search for a node, I need to call the nodePrint() with passing the appropriate argument to it in the main function as follow:

int main() {



    nodePrint("A Pizza");



    return 0;

}

If the node data is a question, the expected result should be:

Object: [NOTHING]

Question: Is it flat, round and edible?

Yes: A Pizza

Yes: Pete

and if the data is a statement, the output should be:

Object: [NOTHING]

Question: A Pizza

My program shows the appropriate result, but there is a SEGFAULT that I cannot figure out what causes it. I really appreciate if someone could help me to debug it.