Congrats to Ravi Ranjan.
But note you can figure out what's on the recursion stack at any time
(for example in a graph search) by adopting a different coding style.
Here is a simple example.
// binary tree nodes
typedef struct node {
struct node *left, *right;
int key;
};
// search stack frame
typedef struct stack_frame {
struct stack_frame *caller;
struct node *tree;
// Any other args or local vars to be accessed within stack go here.
};
// Do an in-order search of the whole tree. We don't
// care about accessing the search key within the stack, so
// it's not included in the struct above. But it could be.
void search(stack_frame *args, int search_key)
{
// Empty tree case.
if (args->tree == NULL) return;
// Set up stack frame for recursive calls with pointer to caller's
frame.
stack_frame call_args[1] = {{ args->caller }};
// Check the left subtree
call_args->tree = args->tree->left;
search(call_args, key);
// See if key matches. If so, print stack frame.
if (args->tree->key == search_key) {
printf("Nodes from key match up to root:\n");
for (struct stack_frame *p = args; p; p = p->caller)
printf("Node %p with key %d\n", p->tree, p->tree->key);
}
// Now check the right subtree.
call_args->tree = args->tree->right;
search(call_args, key);
}
Cheers!
On Mar 1, 11:49 am, atul anand <[email protected]> wrote:
> @Ravi : yeah dere is..and it was discussed before on this group..
>
> check out this link :-
> check soln by Lucifier..
>
> http://groups.google.com/group/algogeeks/browse_thread/thread/9bbdd33...
>
>
>
>
>
>
>
> On Thu, Mar 1, 2012 at 9:18 PM, Ravi Ranjan <[email protected]> wrote:
> > @atul
>
> > two nodes were given in the qstn.......
>
> > i did
>
> > 1) calculate the level of one node through level order traversal similarly
> > for other
> > 2) then find the Least Common Anscestor
> > 3) then dist(LCS - node1) + dist(LCS - node2)
>
> > but i think this was not optimized bcse he was not very much satisfied by
> > this
>
> > So if any of you know some bettr approach then please tell
>
> > thanks a lot :)
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
