## Wednesday, December 29, 2010

### Iterative Tree Traversal

There are three types of tree traversals, namely, inorder, preorder and postorder. For some strange reasons, students @CSE-DU are forced to write iterative versions of these. I am just noting it down here again.

The Node is composed of three fields, namely, Info (data for this node), Left (pointer to left child), Right (pointer to right child). The pseudo-codes are shown below

### Preorder

`Preorder ( Info, Left, Right, root )    top := 1, Stack[top] := NULL, ptr := root;    repeat while ptr != NULL        apply process() to Info[ptr];        if Right[ptr] != NULL then            top := top + 1, Stack[top] = Right[ptr];        if Left[ptr] != NULL then            ptr = Left[ptr];        else            ptr = Stack[top], top := top - 1;    exit`

### Inorder

`Inorder ( Info, Left, Right, root )    top := 1, Stack[top] := NULL, ptr := root;    repeat while ptr != NULL        top := top + 1, Stack[top] = ptr, ptr = Left[ptr];    ptr = Stack[top], top := top - 1;    repeat while ptr != NULL        apply process() to Info[ptr];        if Right[ptr] != NULL then            ptr := Right[ptr];            go to step 03;        ptr := Stack[top], top := top - 1;    exit`

### Postorder

`Postorder ( Info, Left, Right, root )    top := 1, Stack[top] := NULL, ptr := root;    repeat while ptr != NULL        top := top + 1, Stack[top] = ptr, ptr = Left[ptr];    repeat while Stack[top] != NULL and ptr = Right[Stack[top]]        ptr := Stack[top], top := top - 1;        apply process() to Info[ptr];    if Stack[top] != NULL then        ptr := Right[Stack[top]];        go to step 03;    exit`

Really pointless though!