#define NULL 0
class node
int dt;
node *lt,*rt;
node(int x)
class tree
node *create();
int height(node*);
node *mirror(node *);
node* tree::create()
int x;
cout<<"enter data(-1 for no data)";
return NULL;
node *t=new node(x);
cout<<"enter left child of"<<x;
cout<<"enter right child of"<<x;
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!!!

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 article has been dead for over six months. Start a new discussion instead.