Print Ancestors of a node in a Binary Tree:

Print Ancestors of a node in a Binary Tree


Strategy:


#include <stdio.h>
#include <stdlib.h>

struct node
{
    int data;
    struct node *left;
    struct node *right;
};

int isAncestor(struct node* root, int n)
{
    if(root == NULL)
        return 0;

    if(root->data == n)
        return 1;

    if(isAncestor(root->left, n) || isAncestor(root->right, n))
    {
        printf("%d\n", root->data);
        return 1;
    }
    return 0;
}

struct node* newnode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
//  node->nextRight = NULL;

  return(node);
}

int main()
{

    /* Constructed binary tree is
              10
            /   \
          8      2
        /         \
      3            90
       \
        14
    */
    struct node *root = newnode(10);
    root->left        = newnode(8);
    root->right       = newnode(2);
    root->left->left  = newnode(3);
    root->right->right       = newnode(90);
    root->right->right->left       = newnode(14);

    isAncestor(root, 14);
    getchar();
    return 0;
}

Time Complexity: O(n) where n is the number of nodes in the given Binary Tree