Description: Given a key node, print its ancestors.

 
If video does not load, Click here
 
Example:
 

 

The ancestors of 4(key) would be:

   1-2

 

The ancestor of 3(key) would be:

   1

 
Algorithm and Implementation:

 

All nodes on the path from the root to the key can be considered as ancestors.

 

A node is an considered an ancestor if the key node lies either in its left or right subtree.

If it doesn’t, it isn’t an ancestor.

 

/*The following function prints ancestors of the key node. It returns 1 if the key is present in the tree. Else, it returns a 0.*/

int ancestors(struct node *root, int key)

{

 

 if (root == NULL)

    return 0;

 

 if (root->data == key)

    return 1;

 

  if ( ancestors(root->left, key) || ancestors(root->right, key) )

 {

/*if present in left or right subtree*/

PRINT root->data;

   return 1;

 }

 return 0;

}

 
Time Complexity:
 
O(n), where n is number of nodes in the binary tree.
Go to top