# Thread: building a complete binary tree

1. ## building a complete binary tree

Hello,

I want to run a few tests on a full binary tree so I built one. It is supposed to have 3 levels, 8 leaf nodes a-h at last. My print_tree() method causes a segmentation fault. It is not because I did not use malloc() to reserve memory, I just tested it. Can someone explain why it happens?
And what is the easiest way to build a full binary tree with the least amount of code?

Code:
```#include <stdio.h>#include <stdlib.h>

typedef struct Node node;

struct Node{
unsigned int value;
struct Node* left;
unsigned int left_edge : 1;
struct Node* right;
unsigned int right_edge : 1;
};

void print_tree(node* root){
printf("%s = %d\n", "value of node ", root->value);
if (root->left_edge != NULL){
print_tree(root->left_edge);
}
if (root->right_edge != NULL){
print_tree(root->right_edge);
}

}

int main(){

node a = {1,NULL,NULL};
node b = {2,NULL,NULL};
node c = {3,NULL,NULL};
node d = {4,NULL,NULL};
node e = {5,NULL,NULL};
node f = {6,NULL,NULL};
node g = {7,NULL,NULL};
node h = {8,NULL,NULL};

node inner_3 = {0, &a, &b, 0, 1};
node inner_4 = {0, &c, &d, 1, 0};
node inner_5 = {0, &e, &f, 1, 0};
node inner_6 = {0, &g, &h, 1, 0};

node inner_2 = {0, &inner_5, &inner_6, 1, 0};
node* inner_1 = malloc(sizeof(node));
inner_1->value = 2;
inner_1->left_edge = &inner_3;
inner_1->right_edge = &inner_4;
inner_1->left_edge = 1;
node root = {0, &inner_1, &inner_2, 0, 1};

print_tree(&root);

return 0;

}```

2. Yeah, the first thing is fix ALL the warnings before you even try and run any more code.
Code:
```\$ gcc -Wall foo.c
foo.c: In function ‘print_tree’:
foo.c:19:23: warning: comparison between pointer and integer
19 |   if (root->left_edge != NULL){
|                       ^~
foo.c:20:20: warning: passing argument 1 of ‘print_tree’ makes pointer from integer without a cast [-Wint-conversion]
20 |     print_tree(root->left_edge);
|                ~~~~^~~~~~~~~~~
|                    |
|                    unsigned char:1
foo.c:17:23: note: expected ‘node *’ {aka ‘struct Node *’} but argument is of type ‘unsigned char:1’
17 | void print_tree(node* root){
|                 ~~~~~~^~~~
foo.c:22:24: warning: comparison between pointer and integer
22 |   if (root->right_edge != NULL){
|                        ^~
foo.c:23:20: warning: passing argument 1 of ‘print_tree’ makes pointer from integer without a cast [-Wint-conversion]
23 |     print_tree(root->right_edge);
|                ~~~~^~~~~~~~~~~~
|                    |
|                    unsigned char:1
foo.c:17:23: note: expected ‘node *’ {aka ‘struct Node *’} but argument is of type ‘unsigned char:1’
17 | void print_tree(node* root){
|                 ~~~~~~^~~~
foo.c: In function ‘main’:
foo.c:33:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
33 |   node a = {1,NULL,NULL};
|                    ^~~~
foo.c:33:20: note: (near initialization for ‘a.left_edge’)
foo.c:34:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
34 |   node b = {2,NULL,NULL};
|                    ^~~~
foo.c:34:20: note: (near initialization for ‘b.left_edge’)
foo.c:35:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
35 |   node c = {3,NULL,NULL};
|                    ^~~~
foo.c:35:20: note: (near initialization for ‘c.left_edge’)
foo.c:36:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
36 |   node d = {4,NULL,NULL};
|                    ^~~~
foo.c:36:20: note: (near initialization for ‘d.left_edge’)
foo.c:37:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
37 |   node e = {5,NULL,NULL};
|                    ^~~~
foo.c:37:20: note: (near initialization for ‘e.left_edge’)
foo.c:38:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
38 |   node f = {6,NULL,NULL};
|                    ^~~~
foo.c:38:20: note: (near initialization for ‘f.left_edge’)
foo.c:39:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
39 |   node g = {7,NULL,NULL};
|                    ^~~~
foo.c:39:20: note: (near initialization for ‘g.left_edge’)
foo.c:40:20: warning: initialization of ‘unsigned char:1’ from ‘void *’ makes integer from pointer without a cast [-Wint-conversion]
40 |   node h = {8,NULL,NULL};
|                    ^~~~
foo.c:40:20: note: (near initialization for ‘h.left_edge’)
foo.c:43:26: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
43 |   node inner_3 = {0, &a, &b, 0, 1};
|                          ^
foo.c:43:26: note: (near initialization for ‘inner_3.left_edge’)
foo.c:44:26: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
44 |   node inner_4 = {0, &c, &d, 1, 0};
|                          ^
foo.c:44:26: note: (near initialization for ‘inner_4.left_edge’)
foo.c:44:30: warning: initialization of ‘struct Node *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
44 |   node inner_4 = {0, &c, &d, 1, 0};
|                              ^
foo.c:44:30: note: (near initialization for ‘inner_4.right’)
foo.c:45:26: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
45 |   node inner_5 = {0, &e, &f, 1, 0};
|                          ^
foo.c:45:26: note: (near initialization for ‘inner_5.left_edge’)
foo.c:45:30: warning: initialization of ‘struct Node *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
45 |   node inner_5 = {0, &e, &f, 1, 0};
|                              ^
foo.c:45:30: note: (near initialization for ‘inner_5.right’)
foo.c:46:26: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
46 |   node inner_6 = {0, &g, &h, 1, 0};
|                          ^
foo.c:46:26: note: (near initialization for ‘inner_6.left_edge’)
foo.c:46:30: warning: initialization of ‘struct Node *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
46 |   node inner_6 = {0, &g, &h, 1, 0};
|                              ^
foo.c:46:30: note: (near initialization for ‘inner_6.right’)
foo.c:49:32: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
49 |   node inner_2 = {0, &inner_5, &inner_6, 1, 0};
|                                ^
foo.c:49:32: note: (near initialization for ‘inner_2.left_edge’)
foo.c:49:42: warning: initialization of ‘struct Node *’ from ‘int’ makes pointer from integer without a cast [-Wint-conversion]
49 |   node inner_2 = {0, &inner_5, &inner_6, 1, 0};
|                                          ^
foo.c:49:42: note: (near initialization for ‘inner_2.right’)
foo.c:52:22: warning: assignment to ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
52 |   inner_1->left_edge = &inner_3;
|                      ^
foo.c:53:23: warning: assignment to ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
53 |   inner_1->right_edge = &inner_4;
|                       ^
foo.c:55:19: warning: initialization of ‘struct Node *’ from incompatible pointer type ‘node **’ {aka ‘struct Node **’} [-Wincompatible-pointer-types]
55 |   node root = {0, &inner_1, &inner_2, 0, 1};
|                   ^
foo.c:55:19: note: (near initialization for ‘root.left’)
foo.c:55:29: warning: initialization of ‘unsigned char:1’ from ‘node *’ {aka ‘struct Node *’} makes integer from pointer without a cast [-Wint-conversion]
55 |   node root = {0, &inner_1, &inner_2, 0, 1};
|                             ^
foo.c:55:29: note: (near initialization for ‘root.left_edge’)```
That left_edge / right_edge stuff is complete junk, it needs to go.
You only need the left and right pointers.

3. thanks for your reply. The left and right_edge fields are for the tests I want to do, they do not have anything to do with a normal tree structure. Will I still need to fix the warnings?

4. > Will I still need to fix the warnings?
Yes, absolutely, always!

Because you're trying to use those 'edge' fields, which are only 1-bit integers as pointers.

5. I fixed everything and printing works now. do you have any idea why segault came?
Code:
```#include <stdio.h>
#include <stdlib.h>

#define on 1
#define off 0

typedef struct Node node;

struct Node{
unsigned int value;
struct Node* left;
unsigned int left_edge : 1;
struct Node* right;
unsigned int right_edge : 1;
};

void print_tree(node* root){
printf("%s = %d\n", "value of node ", root->value);
if (root->left != NULL){
print_tree(root->left);
}
if (root->right != NULL){
print_tree(root->right);
}

}

int main(){

node a = {1,NULL,0,NULL,0};
node b = {2,NULL,0,NULL,0};
node c = {3,NULL,0,NULL,0};
node d = {4,NULL,0,NULL,0};
node e = {5,NULL,0,NULL,0};
node f = {6,NULL,0,NULL,0};
node g = {7,NULL,0,NULL,0};
node h = {8,NULL,0,NULL,0};

node inner_3 = {0, &a, 0, &b, 1};
node inner_4 = {0, &c, 1, &c, 0};
node inner_5 = {0, &e, 1, &f, 0};
node inner_6 = {0, &g, 1, &h, 0};

node inner_2 = {0, &inner_5, 1, &inner_6, 0};
// the error does not occur because I did not reserve space for the object with malloc.
node* inner_1 = malloc(sizeof(node));
inner_1->value = 2;
inner_1->left = &inner_3;
inner_1->right = &inner_4;
inner_1->left_edge = 1;
node root = {0, inner_1, 0, &inner_2, 1};

print_tree(&root);

return 0;

}```

6. > do you have any idea why segault came?
Yeah, trying to use a 1-bit value as a pointer.

Simply caused by you ignoring the warnings before you tried to run it.

Which is either 0 (aka a NULL pointer) or 1 (next door to NULL).

Most operating systems are going to blackout the first several megabytes of the virtual address space at least, so that any plausible mis-use of a NULL pointer (whether as *p, p[n] or p->member) is going to cause a fault and your program to end.

7. You are still ignoring one warning (unused variable d).

Also, this is a strange comment:

// the error does not occur because I did not reserve space for the object with malloc.
Why do you malloc one random node when you store all the others on the stack?
You could just say:
Code:
`  node inner_1 = {2, &inner_3, 1, &inner_4, 0};`
(I don't understand why inner_1's value would be 2 when all the other inner nodes are 0.)

I'm not sure what you mean by "edge", but if you mean left child or right child, then you aren't setting them correctly.
Code:
```.                     root
i1                      i2
i3          i4          i5          i6
a    b      c    d      e    f      g    h```
If you do mean left and right child, another possibility is to use a parent pointer.
Code:
```#include <stdio.h>
#include <stdlib.h>

typedef struct Node{
int value;
struct Node* left, *right, *parent;
} Node;

void print_tree(Node* node){
if (node) {
printf("%d ", node->value);
if (node->parent)
if (node->parent->left == node)
printf("left");
else
printf("right");
else
printf("root");
putchar('\n');
print_tree(node->left);
print_tree(node->right);
}
}

int main(){
Node a = {1, NULL, NULL, NULL};
Node b = {2, NULL, NULL, NULL};
Node c = {3, NULL, NULL, NULL};
Node d = {4, NULL, NULL, NULL};
Node e = {5, NULL, NULL, NULL};
Node f = {6, NULL, NULL, NULL};
Node g = {7, NULL, NULL, NULL};
Node h = {8, NULL, NULL, NULL};

Node inner_3 = {0, &a, &b, NULL};
Node inner_4 = {0, &c, &d, NULL};
Node inner_5 = {0, &e, &f, NULL};
Node inner_6 = {0, &g, &h, NULL};

a.parent = b.parent = &inner_3;
c.parent = d.parent = &inner_4;
e.parent = f.parent = &inner_5;
g.parent = h.parent = &inner_6;

Node inner_1 = {0, &inner_3, &inner_4, NULL};
Node inner_2 = {0, &inner_5, &inner_6, NULL};

inner_3.parent = inner_4.parent = &inner_1;
inner_5.parent = inner_6.parent = &inner_2;

Node root = {0, &inner_1, &inner_2, NULL};

inner_1.parent = inner_2.parent = &root;

print_tree(&root);

return 0;
}```

8. Originally Posted by john_12
And what is the easiest way to build a full binary tree with the least amount of code?
Just put the data in as initializers.

Code:
```    struct Node {
struct Node *left;
struct Node *right;
};

struct Node * Tree_root = &(struct Node){
.left = &(struct Node){
},
.right = &(struct Node) {
},
}```

9. This is even less code:
Code:
```#include <stdio.h>
#include <stdlib.h>

typedef struct Tree {
int value;
struct Tree *left, *right;
} Tree;

void treePrint(Tree *node, int depth) {
if (!node) return;
if (node->right) treePrint(node->right, depth + 1);
printf("%*s%2d\n", depth * 4, "", node->value);
if (node->left) treePrint(node->left, depth + 1);
}

void treeAdd(Tree **node, int value) {
if (!*node) {
*node = malloc(sizeof **node);
(*node)->value = value;
(*node)->left = (*node)->right = NULL;
}
else if (value < (*node)->value)
else
}

int main() {
Tree *root = NULL;
/*
8
4              12
2       6      10      14
1   3   5   7   9  11  13  15
*/
int values[] = { 8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15 };

for (int i = 0; i < 15; ++i)