CODEWITHSUNDEEP
cbinary-search-tree
THED
THED

Reputation: 1

Finding specific values in a Tree

I'm currently implementing a Binary Search Tree and I'm trying to find the smallest value in the tree with a function like this:

int smallest(Tr *T, void *Item) {
    TNode * n;
    if(Size(T) == 0)
        return 0;
    while(n->left != NULL) {
        n = n->left;
    }

    return 1;
}

Where I have the structs:

typedef struct TNodeTag {
    void *v;
    struct TNodeTag*left, *right, *parent;
} TNode;


typedef struct {
    TNode *root;
    TNode *current;
    void * (*copyItems) (void *, void *);
    int value;
} Tr;

And at first a initialize function:

void Initialize (Tr *T,void * (*copyItems) (void *, void *),{
    T->root = NULL;
    T->copyItems = copyItems;
    T->value = 0;
}

Where void * Item is the address of where a copy of the smallest node should be stored (using the copyValue function)(Which I'm not sure how to create) . Tr * T is a pointer to the first struct. The function smallest, is so posed to return 1 if it can find a smallest value, 0 otherwise (tree is empty).

I'm not sure if my implementation of finding the smallest node is correct, since my function will always return 1,unless the tree is empty?

Upvotes: 0

Views: 46

Answers (1)

ferry
ferry

Reputation: 437

If I understand correctly, the function "smallest" must return 1 if there exists a smallest value in the tree and 0 otherwise. That doesn't sound very useful, since there will always be a smallest value in the tree, so long as the tree is not empty. In this regard, your function is correct.

However, your function tries to de-reference the pointer n before it is being assigned to anything, in the while loop. All bets are off as to what will actually happen and this is probably not something you want. (I imagine the compiler is optimizing this away since n is never used.) I think what you're trying to do is find the smallest value, in which case, you should first assign the address of root node of the tree to n. You could do

...
n = T->root;
while(n->left != NULL) {
    n = n->left;
}

so that, after the loop, n will point to the node with the smallest value. Hope this helps :)

Upvotes: 1

Related Questions