Create a Binary Tree Manually in DSA C - Execution Trace

Concept Flow - Create a Binary Tree Manually

Start: Create root node

↓

Assign root value

↓

Create left child node?

Yes→Assign left child value

↓

Attach left child to root

↓

Create right child node?

Yes→Assign right child value

↓

Attach right child to root

↓

Done

Start by creating the root node, assign its value, then optionally create left and right child nodes, assigning their values and linking them to the root.

Execution Sample

DSA C

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

// Create root
struct Node* root = (struct Node*)malloc(sizeof(struct Node));
*root = (struct Node){1, NULL, NULL};
// Create left child
root->left = (struct Node*)malloc(sizeof(struct Node));
*(root->left) = (struct Node){2, NULL, NULL};
// Create right child
root->right = (struct Node*)malloc(sizeof(struct Node));
*(root->right) = (struct Node){3, NULL, NULL};

This code creates a binary tree with root value 1, left child 2, and right child 3.

Execution Table

Step	Operation	Node Created	Pointer Changes	Visual State
1	Create root node	Node(1)	root -> Node(1)	1 / .
2	Create left child node	Node(2)	root->left -> Node(2)	1 / \ 2 .
3	Create right child node	Node(3)	root->right -> Node(3)	1 / \ 2 3
4	No more nodes to create	None	No pointer changes	1 / \ 2 3

💡 All nodes created and linked; tree construction complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
root	NULL	Node(1)	Node(1)	Node(1)	Node(1)
root->left	NULL	NULL	Node(2)	Node(2)	Node(2)
root->right	NULL	NULL	NULL	Node(3)	Node(3)

Key Moments - 3 Insights

Why do we assign NULL to left and right pointers when creating a new node?

Assigning NULL means the new node has no children yet. This is shown in Step 1 and Step 2 where new nodes are created with left and right as NULL before linking.

Why do we link the left and right child nodes to the root after creating them?

Linking connects the nodes to form the tree structure. In Steps 2 and 3, root->left and root->right pointers are updated to point to the new child nodes, building the tree.

What happens if we skip creating a left or right child node?

If skipped, the corresponding pointer remains NULL, meaning no child on that side. The exit note in the execution table shows the tree is complete even if some children are missing.

Visual Quiz - 3 Questions

Look at the execution table, what is the visual state after Step 2?

A 1 with left child 2 and right child 3

B 1 with left child 2 only

C 1 with right child 3 only

D Only root node 1

💡 Hint

Check the Visual State column in row for Step 2.

At which step does root->right pointer get assigned a node?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at Pointer Changes column for root->right assignment.

If we do not create a left child node, how would the variable tracker change after Step 2?

A root->left remains NULL

B root->left points to Node(2)

C root->left points to Node(3)

D root->left points to root

💡 Hint

Refer to root->left values in variable_tracker after Step 2.

Concept Snapshot

Create a binary tree by:
1. Creating root node with value and NULL children
2. Creating left child node and linking to root->left
3. Creating right child node and linking to root->right
4. Repeat for more nodes as needed
Pointers to children are NULL if no child exists

Full Transcript

To create a binary tree manually, start by creating the root node with a value and set its left and right pointers to NULL. Then create left and right child nodes as needed, assigning their values and setting their pointers to NULL. Link these child nodes to the root by assigning them to root->left and root->right respectively. If a child is not created, its pointer remains NULL, indicating no child on that side. This process builds the tree step-by-step, connecting nodes through pointers.

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