Thread: recriating a bst tree from inorder

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?