Popular Posts

Wednesday, July 13, 2011

Get Level of a node in a Binary Tree

Given a Binary Tree and a key, write a function that returns level of the key.
For example, consider the following tree. If the input key is 3, then your function should return 1. If the input key is 4, then your function should return 3. And for key which is not present in key, then your function should return 0.






Solution:
             While calling left sub tree or right sub tree increment the level by 1. When the Key is found return the current level.

Complexity:   O(n), where n is the number of nodes.

Code:
int getNodeL(Tnode *root, int key, int level) {
    
    int leftlevel = 0, rightlevel = 0;
    
    if (root == NULL)
        return 0;
    
    if (key == root->data)
        return level;
    
    leftlevel = getNodeL(root->left, key, level + 1);
    
    if (leftlevel == 0)
        rightlevel = getNodeL(root->right, key, level + 1);
    
    return leftlevel + rightlevel;
}

No comments:

Post a Comment