Need Help With This CODE of Data Structure(Binary TREE).

[veddotcom]

/* Program to build a binary search tree from arrays. */

#include <stdio.h>
#include <conio.h>
#include <alloc.h>

struct node
{
struct node *left ;
char data ;
struct node *right ;
} ;

struct node * buildtree ( int ) ;
void inorder ( struct node * ) ;

char arr[ ] = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '\0', '\0', 'H' } ;
int lc[ ] = { 1, 3, 5, -1, 9, -1, -1, -1, -1, -1 } ;
int rc[ ] = { 2, 4, 6, -1, -1, -1, -1, -1, -1, -1 } ;

void main( )
{
struct node *root ;

clrscr( ) ;

root = buildtree ( 0 ) ;
printf ( “In-order Traversal:\n” ) ;
inorder ( root ) ;

getch( ) ;
}

struct node * buildtree ( int index )
{
struct node *temp = NULL ;
if ( index != -1 )
{
temp = ( struct node * ) malloc ( sizeof ( struct node ) ) ;
temp -> left = buildtree ( lc[index] ) ; //LINE 1
temp -> data = arr[index] ; //LINE 2
temp -> right = buildtree ( rc[index] ) ; //LINE 3
}
return temp ;
}

void inorder ( struct node *root )
{
if ( root != NULL )
{
inorder ( root -> left ) ;
printf ( "%c\t", root -> data ) ;
inorder ( root -> right ) ;
}
}

OUTPUT Of the Above Programm is

In-Order Traversal:
D B H E A F C G

I want to know How the Function BUILDTREE is Working, The Problem is When we Calling the Function buildtree recursively by the expression LINE 1,HOw Compliter would be Able to Read The LINE 2 and LINE 3, After Recursive Call The Function Buildtree the Compiler would return to 1st Statement i.e "struct node *temp = NULL ;",After that it will check Condition, and if Condition is True it will Allocate the new Node after that It will again call Buildtree funtion, now again compiler will be back to first statement , Then How LINE 1 and LINE 2 Will Work.

 

[maddy354]

when u recursively call a function, for every unknown value, the expression is pushed into a virtual stack.. this continues till it encounters the final value of the tree (array in ur case). now, it substitutes this value in the top expression in stack and pops it and this value in turn is used in the next expression. this's how a recursion works.

 

[veddotcom]

Thanks for The Reply, Now i m Able to understand the Process of RECURSION.

 

[rohan_mhtr]

Recursive functions, work like a sort of loop.

In most loops, you have a variable which is increased at every loop, until certain condition(s) is met.

Recursive functions call themselves with different variables, until a certain condition is met.

eg. sum for the first 10 numbers using a for loop
sum = 0;
for(i=0; i<10; i++)
{
sum +=i;
}


sum of first 10 numbers using a recurrent function

int Sum(currentValue, endValue)
{
if (currentValue<endValue)
{
return currentValue+Sum(currentValue+1,endValue...
}
}

in the main() function, you then call the function as
value = Sum(0,10);

--------------
How the second example work:
currentValue = 0
endValue = 3

I changed the end value, so I don't have to write so much.

0<3 (true)
Sum(0,3) = 0 + Sum(0+1,3)

So now we have to compute Sum(1,3)

currentValue =1
endValue = 3

1<3(true)
Sum(1,3) = 1+ Sum(2,3)

now we compute Sum(2,3)

currentValue = 2
endValue = 3

2<3(true)
Sum(2,3) = 2+Sum(3,3);

now we compute Sum(3,3)
currentValue = 3
endValue = 3

3<3 (false)
so we stop here. There is no Sum(3,3)

So Sum(2,3) = 2;
Sum(1,3) = 1+Sum(2,3) = 1+ 2 = 3
Sum(0,3) = 0 +Sum(1,2) = 0+3 = 3
value = Sum(0,3) = 3.

Note, it's very important to specify an ending condition. The program stores the temporary values of Sum(1,3) and Sum(2,3) in a memory zone called the "heap", which has the structure of a stack. But this stack is limited. If you forget to mention the ending condition, the program will keep adding value to the "heap" stack which will eventually run out of storage space. And at that moment your program will crash.

The general error message in this case is "stack overflow error"... or at least it is in Pascal.

This is how i was thaught in college .
In your case a recursive fumction is used to call an unknown value which will evalvate until final condition is met and the new value obtained is substitued in the topmost expression and this new value is used in the next expression .