Print ancestors of a node in a Binary Tree Node

Given a Binary tree and an integer, print all the ancestors of the node. For example: If the given tree is as below:

Input: 5      Output: 10
Input: 40     Output: 30 10
Input: 1      Output: 4 5 10

Solution:

If Node of the binary tree is defined as below:

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

Algorithm:

To print the ancestors, the logic is as below:

• Traverse the entire tree.
• If the node is desired node, then print it and return true.
• If it is the leaf node then return false
  • If it is neither the desired node nor the leaf node then call this function for left and right sub-trees.
  • If anyone of them returns true, then print this node as well and return true.
  • If both returns false, then return false from here also.

At any point true means the node is an ancestor of the given node. A false means that the given node is neither in the left nor in the right-sub-tree of this node, hence this node is not the ancestor.

Code:

    bool printAncestors(Node *r, int d)
    {
        if(r == NULL)
            return false;
        if(r->data == d )
            return true;
        if( printAncestors(root->left, d) || printAncestors(root->right, d) )
        {
            cout << root->data << " ";
            return true;
        }
        else
        {
            return false;
        }
    }