This is a problem of attribute evaluation. Pick the right attributes,
and it's not hard.
Note this code is not tested, but it ought to work fine.
// return value is the last node visited in reverse order.
// prev is the previous node in reverse order
NODE *inorder_set(NODE *node, NODE *prev)
{
if (node) {
node->next = inorder_set(node->right, prev);
return inorder_set(node->left, node);
}
return prev;
}
Initial call should pass NULL to prev.
You can convert this to iterative form using the standard approach
discussed here some time back. The second recursive call is a tail
call, so begin by converting this to a loop:
NODE *inorder_set(NODE *node, NODE *prev)
{
while (node) {
node->next = inorder_set(node->right, prev);
prev = node;
node = node->left;
}
return prev;
}
Now "simulate" the first recursive call with a stack:
NODE *inorder_set(NODE *node, NODE *prev)
{
NODE *rtn_val;
call:
while (node) {
// save the current args on the stack
stack[p++] = node;
// not needed: stack[p++] = prev;
// reset the args and simulate the call
node = node->right;
goto call;
rtn:
// remove return val and restore the args from the stack
rtn_val = stack[--p];
// not needed as prev is dead here: prev = stack[--p];
node = stack[--p];
node->next = rtn_val;
prev = node;
node = node->left;
}
// Simulate recursive return unless stack is empty.
if (p > 0) {
stack[p++] = prev; // return value
goto rtn;
}
return prev;
}
I'll let you figure out how to manipulate this code in order to get
rid of the gotos and optimize.
On Jul 4, 2:04 pm, Navneet Gupta <[email protected]> wrote:
> Tree has an extra pointer "next" apart from left and right. Objective
> is to set next pointer to point to node successor in the tree.
> Following the next pointer, we would be able to produce sorted list.
>
> Looking for both a recursive and non-recursive approach.
>
> --Navneet
--
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.
