0
#include<iostream.h>
#include<conio.h>
#define NULL 0
class node
{
public:
int dt;
node *lt,*rt;
node(int x)
{
 dt=x;
 lt=rt=NULL;
}
};
class tree
{
public:
node *create();
int height(node*);
node *mirror(node *);
};
node* tree::create()
{
int x;
cout<<"enter data(-1 for no data)";
cin>>x;
if(x==-1)
return NULL;
node *t=new node(x);
cout<<"enter left child of"<<x;
t->lt=create();
cout<<"enter right child of"<<x;
t->rt=create();
return t;
}

plz tell me what exactly happens in stack when recursively creating first the left subtree and then the right subtree
i am well familiar with c++
but ia ma little weak in recursion
help greatly appreciated!!!

2
Contributors
1
Reply
3
Views
5 Years
Discussion Span
Last Post by raptr_dflo
0

The same thing happens on the stack with recursion as with any other function call. In this case, when you first call node * root = t.create(), a frame is added to the stack with space for the returned node* and the address of the following instruction to return to, any arguments to be passed (in this case, none), and local variables (int x, and node *t). Execution then jumps to the beginning of the create() method. When the code reaches t->lt = create();, it adds another frame to the stack and repeats the process. At whatever point the user types -1, the NULL pointer is copied into the returned node* space on the stack frame, control drops back to the saved execution point for the previous level, the return-value is saved into the appropriate variable, and the stack-frame is removed. Then execution proceeds by creating a new stack frame for the right-hand subtree.

Again, this is exactly the same as for any other function call, except that the contents of the stack-frame relate to a new invocation of the same function instead of a different function. And as a result a number of otherwise-potential compiler efficiencies (such as simply inlining the code instead of creating and utilizing an additional stack-frame) often cannot be used. But from the standpoint of an unoptimized "dumb" compiler, there's no difference at all.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.