techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

how to traverse binary tree non-recursively in-order,postorder?

Do we need another mark for each visited node besides the normal node {value, left, right}?

thanks
Rolf Send private email
Thursday, March 09, 2006
 
 
you can use a threaded binary tree for in-order traversal, or a stack for postorder/preorder. no extra field needed for each node
david wnag Send private email
Thursday, March 09, 2006
 
 
I saw somebody else use an extra field "visited" indicating if the current node has been visted, especially in InOrder and PostOrder traversal by using a Stack. You got some sample  idea?

thanks
Ken Send private email
Thursday, March 09, 2006
 
 
I too think stack and queues is the way to convert recurssive code to iterative.
Abhishek Goyal Send private email
Thursday, March 09, 2006
 
 
a stack enables in-order traverse. a stack and a visited mark enable post-order traverse.
Ray Send private email
Thursday, March 09, 2006
 
 
I used a stack to do the in-order. Now for the postorder, I am thinking if I can still do it without some mark ...

Any idea?

thanks
Ken Send private email
Friday, March 10, 2006
 
 
Ken, to do the postorder without marking you need to compare child pointers of the top node on the stack with your current node. If the current node is its left children then you need to access its right child next. Otherwise it's about the time to access the top node and then pop it from the stack. A visited mark only makes the algorithm clear. It's not necessary.
Ray Send private email
Saturday, March 11, 2006
 
 
For postorder traversal non recursively : use stacks
start with inserting root into the stack, then pop root and insert its left and right node. continue popping printing elements from stack and then adding popped nodes left n right nodes into stack.
It will print nodes in post order traversal.
misty Send private email
Thursday, April 13, 2006
 
 
Ray: You're correct that a visited mark is not needed. However, the algorithm is slightly more complex than how you describe it. See my code below.

Misty: What you describe is not post-order at all. Rather, it's pre-order (but mirrored). I.e., instead of going (node, left, right), you're going (node, right, left).

Here's my attempt at succinct solutions for pre-order, in-order and post-order traversal (all non-recursive):

void preorder(const Node* node) {
    std::stack<const Node*> stack;
    while (node != NULL || !stack.empty()) {
        if (node == NULL) {
            node = stack.top(); stack.pop();
        }
        process(node->value);
        if (node->right != NULL)
            stack.push(node->right);
        node = node->left;
    }
}

void inorder(const Node* node) {
    std::stack<const Node*> stack;
    while (node != NULL || !stack.empty()) {
        if (node == NULL) {
            node = stack.top(); stack.pop();
            process(node->value);
            node = node->right;
        }
        if (node != NULL) {
            stack.push(node);
            node = node->left;
        }
    }
}

void postorder(const Node* node) {
    std::stack<const Node*> stack;
    while (node != NULL || !stack.empty()) {
        if (node == NULL) {
            while (!stack.empty() && node == stack.top()->right) {
                node = stack.top(); stack.pop();
                process(node->value);
            }
            node = stack.empty() ? NULL : stack.top()->right;
        }
        if (node != NULL) {
            stack.push(node);
            node = node->left;
        }
    }
}
Sreeram Ramachandran Send private email
Saturday, April 15, 2006
 
 
You are right sreeram
misty Send private email
Sunday, April 16, 2006
 
 
misty is chutia
misty's father
Friday, May 05, 2006
 
 
you are
misty
Sunday, May 07, 2006
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz