CODEWITHSUNDEEP
algorithmrecursiontree
shrinidhisondur
shrinidhisondur

Reputation: 759

How do I mimic a recursive function model to an iterative one with a stack?

Let's consider the problem where I construct a Binary Search Tree from its inorder and postorder traversal. Now in the recursive implementation I would have done something like:

node.left = recursive (start, mid-1); node.right = recursive (mid + 1, end);

Now how would I go about implementing this with a stack ? Cause once a node is popped from the stack I can't come back to it. Is this iterative approach only practical for a traversal ?

This is the gist of the whole code where _constructInPost is recursive:

Node<T> _constructInPost (List<T> in, List<T> post) {

    if (in.size() == 0)
        return null;

    Node<T> root = new Node <T>(post.get(post.size()-1));

    int index = 0;
    for ( ; index < post.size(); index++) {
        if (in.get(index) == root.data) 
            break;
    }

    root.left = _constructInPost (in.subList(0, index), post.subList(0, index));
    root.right = _constructInPost (in.subList(index+1, in.size()), post.subList(index, post.size()-1));

    return root;
}

Upvotes: 0

Views: 406

Answers (1)

btilly
btilly

Reputation: 46399

The answer is, "Learn Forth." :-)

Your stack will contain instructions about what to do. So if you want 2 recursive calls, you will place 2 commands on the stack. If you have work to do, you will do that work. If you want to do 2 recursive calls and then other stuff with the result, you need to place on your stack instructions to do other stuff, then the recursive calls. (That way you don't get to the other stuff until after the recursion happens.) Your basic loop then has the following pattern:

while stack.length():
    command = stack.pop()
    if command.name == 'recursive_call':
        do recursive code that may add to the stack
    elif command.name == 'base case':
        do base case

Upvotes: 2

Related Questions