Jun 132012
 

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;
        }
    }

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

(required)

(required)