The IT Service Excellence Tool Kit has best practices to keep your clients happy and business booming. Inside, you’ll find everything you need to increase client satisfaction and retention, become more competitive, and increase your overall success.

Hi,

I need help on my program. The program is to write an iterative version (using stack )of a postorder traversal on a binary tree.

The function for inserting tree works perfectly but when i call on the function iter_postorder()...nothing happens. Please tell me where I went wrong.

#define CompLT(a,b) (a<b)

#define CompEQ(a,b) (a==b)

#define MAX_STACK_SIZE 100

typedef struct

{

char name [5];

struct Node *link;

} tree;

tree tree1;

typedef struct Node

{

struct Node *left;

struct Node *right;

struct Node *parent;

int data;

}node;

void iter_postorder(node *a)

{

int top=-1;

node *stack[MAX_STACK_SIZE];

for(;;)

{

for(;a;a=a->left)

{

if(top>=MAX_STACK_SIZE-1)

{

fprintf(stderr,"\nStack is full\n");

return;

}

stack[++top]=a;

}

if (top==-1)

{

fprintf(stderr,"\nStack is empty\n");

return;

}

a=stack[top--];

if(!a->right)

{

printf("%d ",a->data);

a=NULL;

}

else

a=a->right;

}

}

void tread (tree *a)

{

int key;

node *x, *current, *parent;

printf("\nWhat is the name of this tree? ");

fgets(a->name,5,stdin);

printf("\nInput the keys of this tree (-1 to end): \n");

scanf("%d",&key);

while (key!=-1)

{

x=(node*)malloc(sizeof(node));

x->data=key;

x->left=NULL;

x->right=NULL;

current=a->link;

parent=0;

while(current)

{

parent=current;

current=CompLT(x->data,current->data) ? current->left:current->right;

}

if(parent)

{

if(CompLT(x->data,parent->data))

parent->left=x;

else

parent->right=x;

}

else

a->link=x;

scanf("%d",&key);

}

}

int main(void)

{ /*calling functions*/

tread(&tree1);

iter_postorder(tree1.link);

}

I need help on my program. The program is to write an iterative version (using stack )of a postorder traversal on a binary tree.

The function for inserting tree works perfectly but when i call on the function iter_postorder()...nothing

#define CompLT(a,b) (a<b)

#define CompEQ(a,b) (a==b)

#define MAX_STACK_SIZE 100

typedef struct

{

char name [5];

struct Node *link;

} tree;

tree tree1;

typedef struct Node

{

struct Node *left;

struct Node *right;

struct Node *parent;

int data;

}node;

void iter_postorder(node *a)

{

int top=-1;

node *stack[MAX_STACK_SIZE];

for(;;)

{

for(;a;a=a->left)

{

if(top>=MAX_STACK_SIZE-1)

{

fprintf(stderr,"\nStack is full\n");

return;

}

stack[++top]=a;

}

if (top==-1)

{

fprintf(stderr,"\nStack is empty\n");

return;

}

a=stack[top--];

if(!a->right)

{

printf("%d ",a->data);

a=NULL;

}

else

a=a->right;

}

}

void tread (tree *a)

{

int key;

node *x, *current, *parent;

printf("\nWhat is the name of this tree? ");

fgets(a->name,5,stdin);

printf("\nInput the keys of this tree (-1 to end): \n");

scanf("%d",&key);

while (key!=-1)

{

x=(node*)malloc(sizeof(nod

x->data=key;

x->left=NULL;

x->right=NULL;

current=a->link;

parent=0;

while(current)

{

parent=current;

current=CompLT(x->data,cur

}

if(parent)

{

if(CompLT(x->data,parent->

parent->left=x;

else

parent->right=x;

}

else

a->link=x;

scanf("%d",&key);

}

}

int main(void)

{ /*calling functions*/

tread(&tree1);

iter_postorder(tree1.link)

}

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get this solution by purchasing an Individual license!
Start your 7-day free trial.

I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

The array you declared does not do what you think.

Instead, up at the typedef, add another def for pointer to node, something like...

typedef struct Node

{

struct Node *left;

struct Node *right;

struct Node *parent;

int data;

}node, *pnode;

and then change the declaration to be...

pnode stack[MAX_STACK_SIZE];

see if that helps

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trialThe other observation here is that only the leaf nodes get displayed on the screen. The reason is simple - all the non-leaf nodes get popped from the stack but do not get displayed. The solution is to push them back onto the stack. This brings us to one more question - if they are pushed back onto the stack, then the next time they are popped they will still have a right node & hence it will translate into an infinite loop!

This infinite loop can be avoided by checking if the popped out node's right child has already been processed. So when you are printing the popped out node, check if this node is the right child of the next node on the stack. If yes the next node has been completely processed & hence needs to be popped & printed.

BlackBeauty, note that I arrived at the following solution based on your code. My objective was to work on your code not to rewrite it. Hence this may not be the most elegant solution but it works

Also I apologize if my explanation has not been very clear

Replace the following code

a=stack[top--];

if(!a->right)

{

printf("%d ",a->data);

a=NULL;

}

else

a=a->right;

with the following code

a=stack[top--];

if(!a->right)

{

printf("%d ",a->data);

// Print out all the non-leaf nodes whose right child has been processed

while (top >= 0 && stack[top]->right == a){

a = stack[top--];

printf("%d ",a->data);

}

a=NULL;

}

else {

// Not a leaf node, so push it back

stack[++top] = a;

a=a->right;

}

Hope this helps

Wilfred

wpinto for answering my question completely. you get an A++.

Regardless, I am glad to be of some help

Cheers,

Wilfred

C

From novice to tech pro — start learning today.

Experts Exchange Solution brought to you by

Enjoy your complimentary solution view.

Get this solution by purchasing an Individual license!
Start your 7-day free trial.