Page 114 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 5: Trees

} Notes
p = stack[top];
top = top-l;
printf(p->data);
p = p->rchild;
if(p != NULL)
/*push right child*/
{
top = top+1;
stack[top] = p;
p = p->lchild;
}
}
}
}
Analysis

Consider the iterative version of the inorder given above. If the binary tree to be traversed is
having n nodes, then the number of nil links is n + 1. Since every node is placed on the stack
once, the statements stack[top] := p and p := stack[top] are executed n times. The test for nil links
will be done exactly n+ 1 times. So every step will be executed no more than some small constant
times n, hence the order of algorithm O(n). Similar analysis can be done to obtain the estimate of
the computation time for preorder and post order.

Preorder Traversal

void preorder(tnode *p)
{
if(p != NULL)
{
printf(p->data);
preorder(p->lchild);
preorder(p->rchild);
}
}
Postorder Traversal

void postorder(tnode *p)
{
if(!p)
{
postorder(p->lchild);
postorder(p->rchild);
printf(p->data);

LOVELY PROFESSIONAL UNIVERSITY 109