Limited to trees where node key values are unique. Seems to have the advantage of better access locality. But I suspect the average time per node is typically greater than for Morris Traversal.
typedef struct Node_ { int val; struct Node_ *left, *right; } Node; extern void visit(Node *); Node * const Null = 0; void traverse(Node *root) { Node *curr = root; Node *stack = Null; Node *temp; enum { false, true } popped = false; for ( ; ; ) { if (!popped) while (curr->left != Null) { /* Use left pointer to push current node onto ** linked list stack, and make left child ** current. */ temp = stack; stack = curr; curr = stack->left; stack->left = temp; } else popped = false; visit(curr); if (curr->right == Null) { if (stack == Null) /* Traversal done. */ break; while (((stack->right) != Null) && (stack->val > stack->right->val)) { /* Pop top of stack and make it current, ** and restore right child pointer. */ temp = curr; curr = stack; stack = stack->right; stack->right = temp; if (stack == Null) /* Traversal done. */ break; } if (stack == Null) /* Traversal done. */ break; /* Pop top of stack and make it current, ** and restore left child pointer. */ temp = curr; curr = stack; stack = stack->left; stack->left = temp; popped = true; } else { /* Use right pointer to push current node onto ** linked list stack, and make right child ** current. */ temp = stack; stack = curr; curr = stack->right; stack->right = temp; } } } -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@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.