CSE 202 Pseudo Codes 1

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!