2

There can be two kinds of nodes :-

  1. Nodes in the subtree rooted with the given node.
  2. Ancestor nodes of the given node.

for (1) part below function seems to work fine

void printkdistanceNodeDown(node *root, int k)
{
    // Base Case
    if (root == NULL || k < 0)  return;

    if (k==0)
    {
       printf("%d", root->data);
       return;
    }

    // Recur for left and right subtrees
    printkdistanceNodeDown(root->left, k-1);
    printkdistanceNodeDown(root->right, k-1);
 }

I am stuck with (2) part i.e to find the ancestor nodes at distance 'k' from target node. How to find nodes of second type ?

1

3 Answers 3

1

As a first step, visit the parent with a third recursive call like

printkdistanceNodeDown(root->parent, k-1);

Now, this doesn't quite work, because in a tree like

  2
 /
1,

printing nodes at distance 3 from 2 will print 1, because we can follow the path 2->1->2->1. The nice property of trees is that, if the path doubles back like this, then there is, in at least one instance, a subpath like x->y->x. Accordingly, one possible fix is to add another parameter, node *previous, that indicates where the path just came from. For the root invocation, previous should be NULL or some value that compares unequal to every valid node. The recursive calls are rewritten to

if (root->parent != previous) printkdistanceNodeDown(root->parent, k-1, root);

and likewise with root->left and root->right.

1

You can find the distance from the root to the target with no problem. You can find the distance from the root to a given ancestor node in the same way.

The rest is left for your leaning benefit, also check if your homework asks for notes at the given distance, or they may want notes within the given distance

(I am assuming that you don't have a "up" pointer on the nodes.)

0

Let's run through a sample Binary-tree and talk about case (2) where the nodes are not the descendants of the target node

                                               100
                                             /    \
                                            8      6
                                           / \    /  \
                                          7   4  1    9
                                         /\  /  /     /\
                                        2  3 5  10   15 25

Let's say, target Node = 15 and K=4
Output Expected = 10, 8

Algorithm:

Step 1: Maintain Two Stacks. In one of the stacks put all the ancestors of Node 15 until we hit root or until the number of ancestors exceed K. This means in worst case, we will have to store the ancestors all the way up to root. In the second stack store L or R (Left or Right) depending on the path followed while storing the ancestors in the 1st stack. Also, maintain a running counter, say cntr, of the number of elements being pushed. The stacks for our example here would look like:

  1st Stack:                                2nd Stack:

    |   |                                    |   |                                  
    |100|                                    | R |
    |6  |                                    | R |
    |9  |                                    | L |

and the cntr = 3

Step2: Pop the elements from both the stacks and invoke your function printkdistanceNodeDown(node *root, int k) with the parameters: root=100->Left (node with value 8) and k=k-cntr-1.

Step3: Decrement cntr and repeat step 2 till the stack is not empty.


Note1: While processing the last elements of the stacks, viz. '9' and 'L' the printkdistanceNodeDown() wouldn't print anything, which is indeed what is intended.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.