Program to Print Ancestors of a Node in Binary Tree

  • Write a C program to check if there exist a path from root to leaf whose sum is N.

Given a binary tree and a node N, we have to print all ancestor nodes of N in given binary tree. In other words, we have to print all the nodes in a path from root node to node N. Here we are going to use a recursive approach to print ancestors of a node.

Algorithm to print all ancestors of a node in binary tree
Let "root" be the pointer to the root node of given binary tree.
  • if root is equal to NULL, return false(node not found).
  • If root is equal to N, return true(node found).
  • Recursively search N in left and right sub tree. If any one the sub tree contains N, then root must be an ancestor of N.
  • If neither left sub tree nor right sub tree contains N, then N is not ancestor of N.
Time Complexity : O(n), we are traversing given binary tree only once.

C program to print all ancestors of a node in binary tree

#include <stdio.h>

#define TRUE 1
#define FALSE 0

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

struct node* getNewNode(int data) {
  /* dynamically allocate memory for a new node */ 
  struct node* newNode = (struct node*)malloc(sizeof(struct node));
 
  /* populate data in new Node */
  newNode->data = data;
  newNode->left = NULL;
  newNode->right = NULL;
  
  return newNode;
}

/*
This function returns below tree
            1
           / \
         2    3
        / \  / \
       4  5 6  7
      / \       \
     8  9       10
*/
struct node* generateBTree(){
    // Root Node
    struct node* root =  getNewNode(1);
    // Level 2 nodes 
    root->left = getNewNode(2);
    root->right = getNewNode(3);
    // Level 3 nodes
    root->left->left = getNewNode(4);
    root->left->right = getNewNode(5);
    root->right->left = getNewNode(6);
    root->right->right = getNewNode(7);
    // Level 4 nodes
    root->left->left->left = getNewNode(8);
    root->left->left->right = getNewNode(9);
    
    root->right->right->right = getNewNode(10);
    
    return root;

}

/* 
   Prints all Ancestors of a node(num)
*/
int printAncestorsOfNode(struct node* root, int num) {
   /* Recursion termination condition */
  if (root == NULL)
     return FALSE;
 
  if (root->data == num)
     return TRUE;
 
  if (printAncestorsOfNode(root->left, num) ||
       printAncestorsOfNode(root->right, num) ) {
      /* If num is present is any any of the two sub tree
       of root, then root is an ancestor of num */
      printf("%d ", root->data);
      return TRUE;
  } else {
      /* If none of the sub tree of root contains num, 
      then root is not an ancestor of num */
      return FALSE;
  }
}

int main() {
    struct node *root = generateBTree();    
    
    /* Printing ancestor's of nodes */
    printf("Ancestors of 9\n");
    printAncestorsOfNode(root, 9);
    printf("\nAncestors of 6\n");
    printAncestorsOfNode(root, 6);
    
    getchar();
    return 0; 
}
Output
Ancestors of 9
4 2 1
Ancestors of 6
3 1
Posted by
Labels: