CODEWITHSUNDEEP
cdepth-first-searchiterative-deepening
Heidar
Heidar

Reputation: 689

Iterative deepening depth-first search in binary tree

i am having a normal binary tree that i am trying to apply iterative deepening depth first search on using c :

struct node {
    int data;
    struct node * right;
    struct node * left;
};

typedef struct node node;

and i am using a function to insert nodes into tree, now i need to implement the search function to be something like this: function search(root,goal,maxLevel) so it search using depth first search but to a specific max level then stop that was my first try,it doesn't work :

currentLevel = 0;
void search(node ** tree, int val, int depth)
{
    if(currentLevel <= depth) {
        currentLevel++;
        if((*tree)->data == val)
        {
            printf("found , current level = %i , depth = %i", currentLevel,depth);

        } else if((*tree)->left!= NULL && (*tree)->right!= NULL)
        {
            search(&(*tree)->left, val, depth);
            search(&(*tree)->right, val, depth);
        }
    }
}

please help, thanks ...

Upvotes: 1

Views: 2145

Answers (2)

Keith Randall
Keith Randall

Reputation: 23265

The global variable won't work for this. You want to have something like

void search(node ** tree, int val, int remainingDepth) {
    if (remainingDepth == 0) return;

then

        search(&(*tree)->left, val, remainingDepth - 1);
        search(&(*tree)->right, val, remainingDepth - 1);

You probably also want to check left & right for null separately, as each could be independently null.

Upvotes: 1

Valeri Atamaniouk
Valeri Atamaniouk

Reputation: 5163

You never stop...

node *search(node ** tree, int val, int depth)
{
    if (depth <= 0)
    {
        return NULL; // not found
    }

    if((*tree)->data == val)
    {
        return *tree;
    }

    if((*tree)->left)
    {
        node * left = search(&(*tree)->left, val, depth - 1);
        if (left) return left; // found
    }
    if((*tree)->right)
    {
        node * right = search(&(*tree)->left, val, depth - 1);
        return right; // whatever is result of right
    }
    return NULL; // not found
}

Upvotes: 2

Related Questions