Iterative Traversal of tree

[Gaiety]

below is the code for traversing a binary tree without using recursion but the problem with the code is we require array of pointers to store all the nodes address.

in below program the parameter nodes in the function push
is an array of pointers to store all the node addresses and poped once NULL is found.

but the method space complexity is O(n)

can any one suggest me how to do it with out cosuming much space.

void intrav(BST_t * bst)
{
        BST_t *tmp;
        tmp=bst;
        do {
                while( tmp != NULL ) {
                push(nodes,tmp);
                tmp = tmp->left;
                }
                if(!empty()){
                        tmp=pop(nodes);
                        printf(" %d ",tmp -> data );
                        tmp = tmp -> right ;
                }
        }while( !empty() || tmp != NULL );
}

[Tom Gunn]

Technically all you need is a stack to store the nodes needed to get back to the nearest root and traverse the other subtree. So the memory cost is O(logN), not O(N), because the size of the stack has at most as many nodes as height(tree) .

The only way I can think of to traverse without using extra storage is destructive and less efficient. Let us say you want to do an in order traversal. Start with the root and whenever the left node is not a null pointer, rotate right. When the left node is a null pointer, visit the node and move to the right, then keep doing the same thing until the node is a null pointer:

while (node)
{
    if (node->left) node = RotateRight(node);
    else
    {
        visit(node);
        node = node->right;
    }
}

This algorithm is less efficient because of the rotations, and it is destructive because the structure of the tree changes after the traversal into the worst case of a BST. However, the good news is that this is also the first step of a perfect balancing algorithm called DSW. If you want, after the traversal you can add the second step and get a better tree than you probably started with. :)

Another good use for this traversal is destroying the tree and freeing nodes. Because the nodes are all being destroyed anyway, the structure does not matter anymore.

[jl.lakhnai]

inorder traversal using while and for loops not stack