3.0.0 Linked List Theory & Structure

LL implementation uses dynamic memory allocation, so there is no need to know the tree size in advance.
It removes size restrictions and handles skewed trees perfectly without formulaic memory waste, though it requires extra memory for pointers.
Mathematical rule: If there are n nodes in a binary tree, the number of NULL links is exactly p = n + 1.

3.0.1 Create Node

struct node {
struct node * left;
int data;
struct node * right;
};

struct node* createNode(int data){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

3.0.2 Create Tree (Recursive)

struct node *createTree(){
int input, data;
printf("Do you want to enter data, 0 for No, 1 for yes: ");
scanf("%d",&input);
if (!input)
return NULL;
else{
struct node *newNode = malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d",&data);
newNode->data = data;
printf("Left child of %d\n", newNode->data);
newNode->left = createTree();
printf("Right child of %d\n", newNode->data);
newNode->right = createTree();
return newNode;
}
}

3.0.3 Main Driver

int main(){
struct node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
root->left->left = createNode(40);
root->left->right = createNode(50);
printf("root is %d\n", root->data);
printf("Left node is %d\n", root->left->data);
printf("right node is %d\n", root->right->data);
return 0;
}

3.0.4 Full LL Code

struct node {
struct node * left;
int data;
struct node * right;
};

struct node* createNode(int data){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}

struct node *createTree(){
int input, data;
printf("Do you want to enter data, 0 for No, 1 for yes: ");
scanf("%d",&input);
if (!input)
return NULL;
else{
struct node *newNode = malloc(sizeof(struct node));
printf("Enter data: ");
scanf("%d",&data);
newNode->data = data;
printf("Left child of %d\n", newNode->data);
newNode->left = createTree();
printf("Right child of %d\n", newNode->data);
newNode->right = createTree();
return newNode;
}
}

int main(){
struct node* root = createNode(10);
root->left = createNode(20);
root->right = createNode(30);
root->left->left = createNode(40);
root->left->right = createNode(50);
printf("root is %d\n", root->data);
printf("Left node is %d\n", root->left->data);
printf("right node is %d\n", root->right->data);
return 0;
}

Logical Breakdown

Click the ➔ arrow on any line to reveal the underlying logic here.