recriating a bst tree from inorder

i have an inorder traversal array (in every node we have only two sons or no sons)
and i need to construct a BST tree out of it.
if i had freedom i would do a fuction of node build(arr,start,end)
ABCREFG
i would build a recursive function which will get R in the middle
then for the leftside i would send indexes from A to C
and for the right side E to G

but i am asked to write a function which has only node * build(int* arr,lenght);

how??

Originally Posted by cfan

i have an inorder traversal array (in every node we have only two sons or no sons)
and i need to construct a BST tree out of it.
if i had freedom i would do a fuction of node build(arr,start,end)
ABCREFG
i would build a recursive function which will get R in the middle
then for the leftside i would send indexes from A to C
and for the right side E to G

but i am asked to write a function which has only node * build(int* arr,lenght);

how??

You can convert between the two. When you want to write:

Code:

build( arr, start, end );

Instead you write:

Code:

build( arr + start, end - start );

Originally Posted by cfan

i have an inorder traversal array

I know what inorder traversal is but I've never seen it refer to an array: does that mean the numbers are in the order they would be if you traversed a tree with them "inorder"?

Anyway, not sure why you have a problem with build(arr,start,end) vs build(int* arr,lenght). For the recursion, you can set the "start" value by submitting that as the array like this:

Code:

int ray[10];
build(&ray[3],7);

array[0] in build() will now be the same as array[3] in the caller.

i tried to understand using this ***R***
but i cant see to what side left or right

Code:

build( arr + start, end - start );

it refers too?

because if start if 0 at the begginig then our range doesnt cut down at all

for the left and right side we need separated ranges?

Originally Posted by cfan

i tried to understand using this ***R***
but i cant see to what side left or right

Code:

build( arr + start, end - start );

it refers too?

because if start if 0 at the begginig then our range doesnt cut down at all

for the left and right side we need separated ranges?

If your root is at 0, then that's (almost?) what you would want to build the right side -- the right side would start at arr[0], and it would have end-start = end elements in it. You need to figure out a way to figure out the root. For instance if you had 1 2 3 4 5 6 7, I would think that you could make 2, 4, or 6 the root.

its easy you use len not as the length but as the number of cells in each subset

i is allways the middle of lenso the left x(arr+1,len-i)
and for right x(arr+i+1,i)