Saturday, January 21, 2012

[Amazon Online Test] Find the nodes at k distance.

Given a tree with the root and a particular node, find the nodes which are atmost at a distance of k from the particular node and print them in sorted order.


 Approach:

Lets say the given tree is


And the given node is of the value 50, and distance k = 3
Then the desired result is 5, 30, 50, 70, 90





The task can be broken down to below sub tasks
1.To find the desired node
2. Find and store all the elements in its vicinity of distance k
3. Sort the nodes by value and print the same.

Obviously the recursion is the key, we recursively iterate over the nodes of the tree and as soon as the target node is found, we publish this result to the calling function so that all the nodes can be stored

The below code snippet prints the nodes at a distance of atmost k.

int printNodeAtKrec(struct tree * root, struct tree * target, int k, vector <int> &v, int n) {
    if(root == NULL)
        return 0;
    int left = 0, right = 0, level = n;
    if(root == target)
        level = k;
    left = printNodeAtKrec(root->left, target, k, v, level - 1);
    level = max(level, left);
    right = printNodeAtKrec(root->right, target, k, v, level - 1);
    if(right > 0 && level < 0) {
        level = right;
        printNodeAtKrec(root->left, target, k, v, level - 1);
    }
    if(level > 0)
        v.push_back(root->data);
    return level - 1;
}

void printNodeAtK(struct tree * t, struct tree * r, int k) {
    vector <int> v;
    printNodeAtKrec(t, r, k + 1, v, 0);
    sort(v.begin(), v.end());
    for(int i = 0; i < v.size(); i++)
        cout<<v[i]<<endl;
}

9 comments :

  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
    }

    ReplyDelete
  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.

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

    ReplyDelete
  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

    Hope this answers ur query.

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

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

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

    ReplyDelete
  8. 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);
    }
    }

    ReplyDelete