Solved

# from a sorted array to AVL tree

Posted on 2009-12-20
Medium Priority
646 Views
I want to built a AVL tree from a sorted array (of ints).
Below is my code, but I'm doing something wrong...
``````typedef struct TreeNode* SearchTree;

struct TreeNode
{
int Element;
SearchTree  Left;
SearchTree  Right;
};
SearchTree avl(int A[],int N, int left, int right,SearchTree T){
SearchTree temp=NULL;
int mid = (left+right)/2;printf("mid=%d",mid);getchar();
temp= Insert(A[mid],T);
right=mid-1;printf(" right=%d",right);
if (right<left) return temp;
avl(A,N,left,right,T);
left=mid+1;
if (left>=right) return temp;
avl(A,N,left,right,T);
}
SearchTree Insert( int X, SearchTree T )
{
if( T == NULL )
{
/* Create and return a one-node tree */
T = (struct TreeNode*)malloc( sizeof( struct TreeNode ) );
if( T == NULL )
FatalError( "Out of space!!!" );
else
{
T->Element = X;
T->Left = T->Right = NULL;
}
}
else
if( X < T->Element )
T->Left = Insert( X, T->Left );
else
if( X > T->Element )
T->Right = Insert( X, T->Right );
/* Else X is in the tree already; we'll do nothing */

return T;
}
``````
0
Question by:xiromdim
• 5
• 2

LVL 3

Expert Comment

ID: 26093006
Hi,

In function avl(int A[],int N, int left, int right,SearchTree T), why don't you just iterate over the elements of A, inserting them one after the other in the tree?

I don't understand why you keep splitting the array in two and inserting the middle element. This looks incorrect...

Regards,
-- mnh
0

LVL 32

Expert Comment

ID: 26093289
Quick look & question for you. Last line in avl() is a recursive call to avl(). But after this last line, you do not return anything. Shouldn't you return a SearchTree?
0

LVL 32

Expert Comment

ID: 26093312
Follow-up comment: avl() defined to return SearchTree, and it does do this sometimes; but whenever avl() is called, the return value is ignored. If you do not need a return value, then do not return anything (make return void); if you do need a return value, then use the return value.
0

LVL 32

Accepted Solution

phoffric earned 1500 total points
ID: 26093413
When inserting the middle element, I believe you are inadvertently missing other elements. You can confirm this in your debugger stepping through each line (or use lots of printf statements).
0

Author Comment

ID: 26097026
I will try to change the function to void... I 'll come back soon.
0

LVL 32

Expert Comment

ID: 26118005
I submitted recommendations to the author, which was incorporated into the code submitted in the follow-up question. http://www.experts-exchange.com/Programming/Languages/C/Q_25001363.html?cid=1576

My 3rd comment was the result of debugging the author's code and identifying major tree insertion issue.

So, why close this, and why not award points to contributors?
0

Author Closing Comment

ID: 31668311
very good advice, but he didn't give some code
0

LVL 32

Expert Comment

ID: 26118285
Hi xiromdim,
I was just starting the dialog with you, and it ended in an hour. I would have answered further questions.
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address.Ā This address might be address of another variable/address of devices/address of fuā¦
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see soā¦
The goal of this video is to provide viewers with basic examples to understand recursion in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
###### Suggested Courses
Course of the Month14 days, 19 hours left to enroll