Recursive and Non-recursive calls in Traversal of Binary Tree

Recursive Calls

When a function calls some other function, the parameters and return address of the function is put in a stack.

Pre-order Recursion

Pre-order traversal = (N, L, R)

See the recursion of pre-order in the following figures:

In-order Recursion

In-order traversal = (L, N, R)

See the recursion of In-order in the following figures:

Non-recursive Calls

Now, we’ll carry out these traversing with the help of non-recursive calls. We can implement non-recursive versions of the pre-order, in-order and post-order traversal by using an explicit stack. We cannot avoid stack. The stack will be used to store the tree nodes in the appropriate order.

Here, for example, is the routine for in-order traversal that uses a stack.

void inorder(TreeNode<int>* root) {
	Stack<TreeNode<int>* > stack;
	TreeNode<int>* p;
	p = root;
	do {
		while( p != NULL ) {
			stack.push( p );
			p = p->getLeft();
		}
		// at this point, left tree is empty
		if( !stack.empty() ) {
			p = stack.pop();
			cout << *(p->getInfo()) << " ";
			// go back & traverse right subtree
			p = p->getRight();
		}
	} while ( !stack.empty() || p != NULL );
}

Stack<TreeNode* > stack; Means, we want to keep “TreeNode” in the stack and inside a TreeNode, we want to keep integer(int). It has two levels of templates.

Traversal Trace

Let’s compare the recursive in-order and non-recursive in-order. In the left column, we have recursive in-order and on the right column there is non-recursive in-order.

In short

Recursive in-order

• Less statements are required.
• Readability increases.
• It’s elegant procedure.

Non-recursive in-order

• It requires time for making stack.
• More statements are required.
• Readability decreases.
• This isn’t an elegant procedure.

REFERENCE: CS301 Handouts (page 146 to 155)