Create a Binary Tree Manually in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a binary tree?

A binary tree is a structure where each node has up to two children, called left and right. It looks like a family tree with each parent having at most two kids.

beginner

How do you create a node in a binary tree manually in C?

You define a struct with data and two pointers for left and right children. Then you create a node by allocating memory and setting its data and children pointers to NULL.

beginner

What does the left and right pointer in a binary tree node represent?

They point to the left child and right child nodes of the current node. If there is no child, the pointer is NULL.

beginner

Why do we set child pointers to NULL when creating a new node?

Setting child pointers to NULL means the node has no children yet. It helps avoid errors when traversing or adding nodes later.

beginner

What is the first step to manually build a binary tree in C?

First, create the root node by allocating memory and setting its data and child pointers. Then add child nodes by linking them to the root or other nodes.

What does a binary tree node contain?

A Data and two child pointers

B Only data

C Data and one child pointer

D Only two child pointers

A binary tree node has data and two pointers for left and right children.

In C, how do you create a new node for a binary tree?

A Using scanf to read the node

B Using printf to print the node

C Using malloc to allocate memory and setting pointers to NULL

D Using free to allocate memory

malloc allocates memory for the node, and pointers are set to NULL to indicate no children.

What does a NULL pointer in a binary tree node mean?

A No child node exists

B Node has data zero

C Node is root

D Node is deleted

NULL means the pointer does not point to any child node.

Which of these is NOT part of a binary tree node in C?

A Pointer to left child

B Pointer to parent node

C Pointer to right child

D Data value

A basic binary tree node does not usually have a pointer to its parent.

What is the root node in a binary tree?

A A node with no data

B A leaf node

C A node with two children

D The top node with no parent

The root node is the top node from which all others descend.

Explain how to manually create a binary tree in C starting from the root node.

Think about creating nodes one by one and linking them.

Describe the role of left and right pointers in a binary tree node.

They connect nodes like branches in a 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