Saturday, January 21, 2012

1. find_nodes(root,s_node,k)
{
if(k>0 &&s_node)
{
find_nodes(root,s_node->left,k-1)
find_nodes(root,s_node->right,k-1)
find_node(root,s_node->father,k-1)
}
else return s_node
}

2. @Anonymous .. there are couple of issues with this terse piece of code :)
1. There is no parent pointer in the structure.
2. Where is the node in sorted order is getting printed ?
3. You will get stuck in an infinite loop.

3. Please define "distance" between 2 nodes. Is it that both the nodes should have ancestor-descendant relationship?

4. @i am what i am
For e.g the given tree is

2
/ \
5 6
/ \ / \
3 4 8 9

Then if the given node is with value 3 and distance as 3 then the desired output is

2
4
5
6

5. how the distance between node 3 and node 5 is 3???? it should be 1 as 5 is parent node of 3

6. @Anonymous .. sorry for the glitch in the problem statement. Edited the same.

7. void printKDistanceNodeDown(root,k)
{
if(!root) return;
if(k==0)
printf("%d",root->data);
printKDistanceNodeDown(root->left,k-1);
printKDistanceNodeDown(root->right,k-1);
}
int printKDistanceNodeUp(root,a,k)
{
if(a->data==root->data) return 1;
int left = printKDistanceNodeDown(root,a,k);
int right = printKDistanceNodeDown(root,a,k);
if(left==k)
printf("%d",left->data);
if(right==k)
printf("%d",left->data);
if(left)
{
printKDistanceNodeDown(root->right,a,k-left-1);
return left+1;
}
if(right)
{
printKDistanceNodeDown(root->left,a,k-right-1);
return right+1;
}
return 0;
}
void printKDistanceNode(struct node * root, struct node *a int k)
{
printKDistanceNodeUp(root,a,k);
printKDistanceNodeDown(a,k);
}

8. porco dio!!!

9. I assume there is a parent pointer.. otherwise.. it's too cumbersome :P.
I've done a recursive solution, but added a 'ignore' pointer to prevent looping

struct tree {
tree* parent;
tree* left;
tree* right;
int value;
};

void printNodesAtDistK(tree* t, int k) {
printNodesAtDistK(t, k, nullptr);
}

bool isRightChild(tree* t) {
return t->parent->right == t;
}

void printNodesAtDistK(tree* t, int k, tree* ignore) {
// print them in order
if (k==0) {
cout << t->value << endl;
} else {
if (t->parent && t->parent != ignore && isRightChild(t))
printNodesAtDisk(t->parent, k-1, t);

if (t->left && t->left != ignore)
printNodesAtDistK(t->left, k-1, t);

if (t->right && t->right != ignore)
printNodesAtDistK(t->right, k-1, t);

if (t->parent && t->parent != ignore && !isRightChild(t))
printNodesAtDistK(t->parent, k-1, t);
}
}