# How to convert an array representation of Binary tree into actual Bina

Page 1 of 1

## 3 Replies - 9421 Views - Last Post: 11 November 2009 - 05:30 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=138049&amp;s=8feee92be5dd6cec972c9ecdd288b528&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 Pandurang

• New D.I.C Head

Reputation: 0
• Posts: 7
• Joined: 04-October 09

# How to convert an array representation of Binary tree into actual Bina

Posted 10 November 2009 - 08:08 AM

I am having one array representation of binary tree.
I need to tell whether its Binary Search Tree or not.
I am trying to first convert an array into binary tree, which can be checked quickly.
I have written following code.
I am sure , i am messing up with the insert part of it.
Below is my code.
First element in array is the number of elements.Blank spaces in the array are indicated by -1.

```#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define true 1
#define false 0
struct node {
int data, pos;
struct node* left;
struct node* right;
};

struct node* NewNode(int data, int pos) {
struct node* node = malloc(sizeof(struct node));
node->data = data;
node->pos = pos;
node->left = NULL;
node->right = NULL;

return(node);
}

struct node* insert(struct node* node,int data, int pos)
{
if (node == NULL) {
return(NewNode(data, pos));
}

if(node->left == NULL && pos%2==0)
node->left=insert(node->left,data, pos);
else
node->right=insert(node->right,data, pos);

return(node); // return the (unchanged) node pointer
}

void printTree(struct node* node) {
if (node == NULL) return;

printTree(node->left);
printf("%d ", node->data);
printTree(node->right);
}

int minValue(struct node* node) {
struct node* current = node;

// loop down to find the leftmost leaf
while (current->left != NULL) {
current = current->left;
}

return(current->data);
}

int maxValue(struct node* node) {
struct node* current = node;
while (current->left != NULL) {
current = current->right;
}
return(current->data);
}

int isBST(struct node* node) {
if (node==NULL) return(true);

if (node->left!=NULL && maxValue(node->left) > node->data)
return(false);

// false if the min of the right is <= than us
if (node->right!=NULL && minValue(node->right) <= node->data)
return(false);

// false if, recursively, the left or right is not a BST
if (!isBST(node->left) || !isBST(node->right))
return(false);

// passing all that, it's a BST
return(true);
}

int main()
{
struct node* N1=malloc(sizeof(struct node));
int i;
int arr[]={14,17,12,25,9,15,21,29,-1,11,-1,-1,19,-1,27};
N1 = NULL;
for(i=1;i<=arr[0];i++)
{
N1 = insert(N1,arr[i],i);
}
printTree(N1);
printf("\nisBST = %d\n",isBST(N1) );
}

```

Is This A Good Question/Topic? 0

## Replies To: How to convert an array representation of Binary tree into actual Bina

### #2 Pandurang

• New D.I.C Head

Reputation: 0
• Posts: 7
• Joined: 04-October 09

## Re: How to convert an array representation of Binary tree into actual Bina

Posted 10 November 2009 - 08:22 AM

Please note that I am not trying to build a BST but just a binary tree from array( breadth first )

### #3 Pandurang

• New D.I.C Head

Reputation: 0
• Posts: 7
• Joined: 04-October 09

## Re: How to convert an array representation of Binary tree into actual Bina

Posted 10 November 2009 - 07:00 PM

Any expert to help me out here....!

### #4 Pandurang

• New D.I.C Head

Reputation: 0
• Posts: 7
• Joined: 04-October 09

## Re: How to convert an array representation of Binary tree into actual Bina

Posted 11 November 2009 - 05:30 AM

Finally solved the problem, but not using linked list....!
Used the same IsBST logic but on an array....!