Print the level of the tree where a key is located

Admin 1
Viewed 38

1 - Read a sequence of n numbers and insert it into a binary search tree. (I did this part without any problems.)

Node *insert(Node **root, int k)
{
    if(*root == NULL)
    {
        Node *newNode = (Node *)malloc(sizeof(Node ));
        if(newNode == NULL)
            return NULL;
        newNode->key = k;
        newNode->left = NULL;
        newNode->right = NULL;
        (*root) = newNode; 
        return newNode; 
    }
    if(k < (*root)->key)
        return insert(&((*root)->left),k);
    else
        return insert((&(*root)->right),k);
}

2 - Read a number and print at which level it is located. Print -1 if the key is not present in the tree.
This part I don't know how to do, I was only able to calculate the total height of the tree.

int height(Node *aNode,int k) {
    if (aNode == NULL) {
        return -1;
    }

    int lefth = height(aNode->left,k);
    int righth = height(aNode->right,k);

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}

Example:

bst example

If the given number is 60 i must print 1

If the given number is 27 i must print 3

If the given number is 100 i must print -1

binary-search-tree c
1 Answers

You should:

  • Stop traversing and return 0 when the value is found.
  • Return -1 when the value is not found from both children.
int height(Node *aNode,int k) {
    if (aNode == NULL) {
        return -1;
    }

    if (aNode->key == k) return 0; /* add this */

    int lefth = height(aNode->left,k);
    int righth = height(aNode->right,k);

    if (lefth == -1 && righth == -1) return -1; /* add this */

    if (lefth > righth) {
        return lefth + 1;
    } else {
        return righth + 1;
    }
}
user_40623540
Related