Popular Posts

Wednesday, July 13, 2011

Print Ancestors of a given node in Binary Tree

Given a Binary Tree and a key, write a function that prints all the ancestors of the key in the given binary tree.
For example, if the given tree is following Binary Tree and key is 7, then your function should print 4, 2 and 1.
              1
            /   \
          2      3
        /  \
      4     5
     /
    7
 
Solution: 
Traverse the tree recursively until the key is found, 
start printing the data in the nodes as the recursive call 
returns.
 
Complexity: O(n), where n is the no of nodes.
 
Code: 

int printAncestor(Tnode *root,int key)
{
    if(root==NULL)
        return 0;
    if(key==root->data)
        return 1;
    if(printAncestor(root->left, key) ||
            printAncestor(root->right, key))
    {
        printf(" %d ",root->data);
        return 1;
    }
    return 0;
}

 

No comments:

Post a Comment