Jeff Greene - 1 year ago 70
C Question

# Constructing a tree in C with only leaves, given a pre order sequence

I am trying to build a specific type of tree, where each internal node's data relies on the leaves of the tree. I have a pre-order array,

`pre[] = { 0,0,0,1,2,3,0,4,5}`
where each "0" represents an internal node, and anything else represents leaves. If I were to construct this tree, it would look like this:

``````         0
/     \
0       0
/ \     / \
0   3   4   5
/ \
1   2
``````

I am having trouble with the recursive call, specifically in the while loop. After I finish with creating the node with data "2", after I return the root I am left at the internal node right above it. This internal node will continue to run in the while loop and mess up my tree. If I decide to place a return root within the while loop at the end of the condition statements then the construction will stop after filling up the left side of the tree. How can I fix this?

``````  1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <limits.h>
4
5 struct node
6 {
7         int data;
8         int leafNode;
9         struct node *left;
10         struct node *right;
11 };
12
14 struct node* newNode (int data){
15         struct node* temp = (struct node *) malloc(sizeof(struct node));
16         temp->data =data;
17         temp->left = temp->right= NULL;
18         return temp;
19 }
22 struct node* _constructTree( int pre[], int * preIndex, int low, int high, int size, int leaf){
23         if (*preIndex >= size || low > high){
24                 return NULL;}
25
26         printf("We are about to create this node: %d\n", pre[*preIndex]);
27
28         struct node* root = newNode(pre[*preIndex]);
29         *preIndex = *preIndex + 1;
30         if(leaf){
31                 printf("Returning this leaf node: %d\n", pre[*preIndex - 1]);
32                 return root;}
33
34
35         if(low == high){
36                 return root;}
37
38         while(low<high){
39                 if(pre[*preIndex] == 0){
40                 root->left = _constructTree(pre, preIndex, *preIndex, high, size, 0);}
41
42                 if(root->left == NULL){
43                 root->left  = _constructTree(pre, preIndex, *preIndex, high, size, 1);
44                 return root;
45                 }
46                 if(pre[*preIndex] != 0){
47                 root->right = _constructTree(pre, preIndex, *preIndex, high, size, 1);
48                 return root;
49                 }
50                 else{
51                 root->right = _constructTree(pre,preIndex, *preIndex, high, size, 0);}
52                         }
53                 return root;
54         }
55 }
56
57 struct node * constructTree(int pre[], int size){
58         int preIndex = 0;
59         return _constructTree(pre, &preIndex, 0, size -1, size, 0);
60         }
61
``````

``````construct_tree(int pre[], int* index){