Create a Binary Tree Manually in DSA C

Mental Model

A binary tree is a structure where each node can have up to two children, called left and right. Creating it manually means building each node and linking them by hand.

Analogy: Think of a family tree where each person can have up to two children. You create each person and then connect them as parents and children.

    1
   / \
  2   3
 / \
4   5

Dry Run Walkthrough

Input: Create a binary tree with root 1, left child 2, right child 3, and 2's children 4 and 5

Goal: Build the tree manually by creating nodes and linking them correctly

Step 1: Create root node with value 1

1 (root) -> left: null, right: null

Why: Start with the root node as the base of the tree

Step 2: Create left child node with value 2 and link to root's left

1 -> left: 2, right: null
2 -> left: null, right: null

Why: Add left child to root to build left subtree

Step 3: Create right child node with value 3 and link to root's right

1 -> left: 2, right: 3
2 -> left: null, right: null
3 -> left: null, right: null

Why: Add right child to root to build right subtree

Step 4: Create left child node with value 4 and link to node 2's left

1 -> left: 2, right: 3
2 -> left: 4, right: null
3 -> left: null, right: null
4 -> left: null, right: null

Why: Add left child to node 2 to extend left subtree

Step 5: Create right child node with value 5 and link to node 2's right

1 -> left: 2, right: 3
2 -> left: 4, right: 5
3 -> left: null, right: null
4 -> left: null, right: null
5 -> left: null, right: null

Why: Add right child to node 2 to complete left subtree

Result:

1 -> left: 2, right: 3
2 -> left: 4, right: 5
3 -> left: null, right: null
4 -> left: null, right: null
5 -> left: null, right: null

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Define the node structure
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to print tree in preorder (root-left-right)
void printPreorder(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    printPreorder(root->left);
    printPreorder(root->right);
}

int main() {
    // Step 1: Create root node
    Node* root = createNode(1);

    // Step 2: Create left child of root
    root->left = createNode(2);

    // Step 3: Create right child of root
    root->right = createNode(3);

    // Step 4: Create left child of node 2
    root->left->left = createNode(4);

    // Step 5: Create right child of node 2
    root->left->right = createNode(5);

    // Print the tree to verify
    printf("Preorder traversal: ");
    printPreorder(root);
    printf("\n");

    return 0;
}

Node* root = createNode(1);

Create root node with value 1

root->left = createNode(2);

Create left child of root with value 2

root->right = createNode(3);

Create right child of root with value 3

root->left->left = createNode(4);

Create left child of node 2 with value 4

root->left->right = createNode(5);

Create right child of node 2 with value 5

Output

Preorder traversal: 1 2 4 5 3 

Complexity Analysis

Time: O(1) for each node creation because each node is created and linked individually without traversal

Space: O(n) where n is the number of nodes because each node requires memory allocation

vs Alternative: Manual creation is straightforward but not scalable; automated tree building from arrays or input can be more efficient for large trees

Edge Cases

Empty tree (no nodes)

Root pointer is NULL, no nodes to create or link

DSA C

if (root == NULL) return;

Single node tree

Only root node is created, left and right remain NULL

DSA C

Node* root = createNode(1);

When to Use This Pattern

When you need to build a tree from scratch or understand its structure node by node, manually creating nodes and linking them is the first step to grasp tree construction.

Common Mistakes

Mistake: Forgetting to initialize left and right pointers to NULL in new nodes
Fix: Always set left and right pointers to NULL when creating a new node to avoid undefined behavior

Mistake: Linking children to wrong parent nodes
Fix: Carefully assign children to the correct parent's left or right pointer

Summary

Manually creating a binary tree means making each node and linking left and right children by hand.

Use this method when you want full control over the tree structure or for learning purposes.

The key is to create nodes one by one and connect them properly to form the tree.

Practice

1. What is the correct way to manually create a binary tree node in C with value 10?

easy

A. Create a struct node with data = 10 and left, right pointers set to NULL

B. Create an integer variable with value 10

C. Use an array of size 10 to represent the tree

D. Declare a pointer without initializing it

Solution

1. Step 1: Understand binary tree node structure

   A binary tree node in C is usually a struct with data and two pointers (left and right) to child nodes.

2. Step 2: Initialize node with value and NULL children

   To create a node with value 10, set data = 10 and left, right pointers to NULL to indicate no children yet.

3. Final Answer:

   Create a struct node with data = 10 and left, right pointers set to NULL -> Option A

4. Quick Check:

   Binary tree node = struct with data + NULL children [OK]

Hint: Binary tree node = struct with data + NULL children [OK]

Common Mistakes:

• Using an integer variable instead of a struct node
• Not initializing left and right pointers to NULL
• Using arrays to represent nodes directly
• Declaring pointers without allocation or initialization

2. Which of the following is the correct syntax to create a new binary tree node dynamically in C?

easy

A. node newNode = malloc(sizeof(node));

B. struct node newNode = malloc(sizeof(struct node));

C. struct node *newNode = new struct node();

D. struct node *newNode = malloc(sizeof(struct node));

Solution

1. Step 1: Use malloc to allocate memory for a struct pointer

   In C, dynamic memory allocation for a struct pointer uses malloc with sizeof the struct type.

2. Step 2: Correct pointer declaration and malloc usage

   struct node *newNode = malloc(sizeof(struct node)); correctly declares a pointer and assigns malloc result cast implicitly to void*.

3. Final Answer:

   struct node *newNode = malloc(sizeof(struct node)); -> Option D

4. Quick Check:

   Dynamic node creation = pointer + malloc(sizeof(struct node)) [OK]

Hint: Use malloc with sizeof(struct node) for dynamic node creation [OK]

Common Mistakes:

• Declaring struct variable instead of pointer for malloc
• Using C++ style new operator in C
• Missing struct keyword in declaration
• Incorrect type name without struct keyword

3. Given the following code snippet, what is the output when printing root->left->data?

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

struct node *root = malloc(sizeof(struct node));
root->data = 1;
root->left = malloc(sizeof(struct node));
root->left->data = 2;
root->right = NULL;

printf("%d", root->left->data);

medium

A. 0

B. 1

C. 2

D. Segmentation fault

Solution

1. Step 1: Trace node assignments

   root->left is allocated and its data is set to 2.

2. Step 2: Print root->left->data value

   Printing root->left->data outputs 2 as assigned.

3. Final Answer:

   2 -> Option C

4. Quick Check:

   root->left->data = 2 [OK]

Hint: Follow pointer assignments step-by-step to find printed value [OK]

Common Mistakes:

• Confusing root->data with root->left->data
• Assuming uninitialized pointers have zero
• Expecting segmentation fault without null check
• Misreading pointer dereference

4. Identify the error in the following code that tries to create a binary tree node:

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

struct node *root;
root->data = 5;
root->left = NULL;
root->right = NULL;

medium

A. Missing semicolon after struct definition

B. root is not initialized with memory before use

C. Incorrect struct member names

D. root should be an integer, not a pointer

Solution

1. Step 1: Check pointer initialization

   root is declared as a pointer but not assigned memory with malloc or set to a valid node.

2. Step 2: Using root->data without allocation causes error

   Accessing root->data without initialization leads to undefined behavior or crash.

3. Final Answer:

   root is not initialized with memory before use -> Option B

4. Quick Check:

   Pointer must be allocated before dereferencing [OK]

Hint: Always allocate memory before using pointer members [OK]

Common Mistakes:

• Forgetting to allocate memory with malloc
• Assuming pointer is auto-initialized
• Confusing syntax errors with runtime errors
• Misunderstanding pointer vs variable types

5. You want to manually create this binary tree:

    10
   /  \
  5    15
 /    /  \
3    12  20

Which sequence of C statements correctly creates this tree?

hard

A. Create root with 10, root->left with 5, root->right with 15, then root->left->left with 3, root->right->left with 12, root->right->right with 20

B. Create root with 10, root->left with 15, root->right with 5, then root->left->left with 12, root->right->left with 3, root->right->right with 20

C. Create root with 10, root->left with 5, root->right with 15, then root->left->right with 3, root->right->left with 12, root->right->right with 20

D. Create root with 10, root->left with 5, root->right with 15, then root->left->left with 12, root->right->left with 3, root->right->right with 20

Solution

1. Step 1: Map tree structure to pointers

   Root is 10, left child 5, right child 15. Left child of 5 is 3. Left and right children of 15 are 12 and 20 respectively.

2. Step 2: Verify pointer assignments match tree

   Create root with 10, root->left with 5, root->right with 15, then root->left->left with 3, root->right->left with 12, root->right->right with 20 correctly assigns left and right pointers to match the tree shape and values.

3. Final Answer:

   Create root with 10, root->left with 5, root->right with 15, then root->left->left with 3, root->right->left with 12, root->right->right with 20 -> Option A

4. Quick Check:

   Pointer assignments match tree structure [OK]

Hint: Match tree diagram nodes to left/right pointers carefully [OK]

Common Mistakes:

• Swapping left and right children
• Assigning nodes to wrong child pointers
• Missing some child node assignments
• Confusing node values with pointer positions