Zaki Mirza’s Blog

Icon

… About software and beyond!

Quiz #2 – Tree Problem (DS)


My brother put this question to me a couple of years ago. Then i found myself having to deal with it in my datastructures project. here it is: 

Suppose you have a tree. A binary tree (for something like simplicity :p). You are traversing it (using infix, postfix or prefix) to search for a node. You find your required node. You just realized that you need to know the path from this node back to the root node (and/or vice versa). Given the following description of the structure of the tree node that you “cant” change:

struct node{Data data; node *right,*left;};

what will you strategy be to tackle this problem.

To make it more intresting (or maybe just the application of the above problem) suppose you find the node A and a node B in consecutive searches. Now what will your strategy be to show a path from A to B. (not neccesarily from the root of the whole tree, but possibly).

 Dont peek in the comments please. Think about it. Rule of pinky: Be honest to yourself atleast :p

You can make any assumption, but dont forget to state it with your solution.

Advertisements

Filed under: programming, quiz

4 Responses

  1. Samer says:

    i would add the subsequent traversals to a linked list…. for example the place where i start to search till where i end… ill keep adding those nodes to the linked list…. at the end the link list would have the path that you just traversed so you can do whatever you wanted to do :p

    Samer
    Noobie

  2. Nirmal says:

    This definitely is an interesting problem!… of course im assuming that you have not given me any other details…are you giving me any other details? – like the root node ?
    the comment above by samer assumes this.

  3. zakimirza says:

    You can make any assumption you want to. Oh btw, there’s a fix in teh quiz i just saw. there has to be right and left pointers, not next :p. but you can make any assumption

  4. Game says:

    Well a very obvious soln which I can think of is to maintain a bit-vector and maintain a counter at every recursive call. If you go left set the bit 0 else set it 1. If tree is very large, malloc the bitvector at some intermediate node and copy the bits made till that node. So in effect starting from the root and ending at the node which u found, in the bitvector u will have a sequences of 0s and 1s which will tell u the path from the root to this node. Job done.

    For the second part, if u remember the bitvectors of A and B just do bit_vec_A & bit_vec_B if this value equals either bit_vec_A or bit_vec_B then there is a path from one to the other which now is very trivial to find.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

RSS Google Shared Items

  • An error has occurred; the feed is probably down. Try again later.

RSS Google Reader Starred Items

  • An error has occurred; the feed is probably down. Try again later.

Top Clicks

  • None
%d bloggers like this: