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 <navneetnn...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.