Thursday, June 9, 2011

Traverse a tree without recursion

The basic problem of traversing a tree requires recursion. If you dont have recursion then you should have a mechanism to save either side of the tree on to a temporary location, this can be done with a stack.
So the algorithm should be

1) traverse the node, if there is right push on to stack, and go to left node
2) if there is no left then pop from the stack and go to that node.
3) do this til all the nodes are exhausted. i.e. till your node pointer is null

Find the code here, for your reference. Push and Pop can be implemented as a simple stack methods.

/* Traverse a tree without recursion */
/* The basic idea is to use a stack for storing the other side of the tree when going in one direction */

void traverse_without_recursion(node *head) {
    node *next = head;
    while(next != NULL) {
        printf("%d", next->data);
            next = next->left;
        else next = (node *) POP();

No comments:

Post a Comment