Binary Tree Node Structure in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a binary tree node?

A binary tree node is a data structure element that contains data and has two pointers or references: one to the left child and one to the right child.

beginner

Show the basic C structure for a binary tree node.

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

beginner

What do the 'left' and 'right' pointers in a binary tree node represent?

They point to the left child node and right child node respectively, or NULL if there is no child on that side.

intermediate

Why is the binary tree node structure recursive in nature?

Because each node contains pointers to other nodes of the same type, allowing the tree to grow by linking nodes together.

intermediate

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

Use malloc to allocate memory, set the data value, and initialize left and right pointers to NULL. Example: struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = value; newNode->left = NULL; newNode->right = NULL;

What does the 'left' pointer in a binary tree node point to?

A The left child node

B The right child node

C The parent node

D The root node

The 'left' pointer always points to the left child node or NULL if no left child exists.

Which keyword is used in C to allocate memory for a new binary tree node?

A alloc

B new

C malloc

D create

malloc is used in C to allocate memory dynamically for new nodes.

What is the data type of the pointers 'left' and 'right' in the binary tree node structure?

A struct Node*

B int*

C char*

D void*

The pointers 'left' and 'right' point to other nodes of the same type, so their type is struct Node*.

If a binary tree node has no children, what are the values of its 'left' and 'right' pointers?

A They point to the root

B They contain garbage values

C They point to each other

D They are NULL

When a node has no children, both 'left' and 'right' pointers are set to NULL.

Why is the binary tree node structure considered recursive?

A Because it uses recursion in functions

B Because nodes contain pointers to nodes of the same type

C Because it stores recursive data

D Because it has a recursive data type

The structure is recursive because each node contains pointers to other nodes of the same structure type.

Describe the structure of a binary tree node in C and explain the purpose of each part.

Think about how each node connects to others.

Explain how you would create and initialize a new binary tree node in C.

Remember to allocate memory and set pointers carefully.

Practice

1. What does a typical binary tree node structure contain in C?

easy

A. Two data fields and no pointers

B. Only a data field without any pointers

C. A data field and a pointer to the parent node only

D. A data field and two pointers to left and right child nodes

Solution

1. Step 1: Understand binary tree node components

   A binary tree node must hold data and links to its children to form the tree structure.

2. Step 2: Identify correct structure

   The node typically has one data field and two pointers: one for the left child and one for the right child.

3. Final Answer:

   A data field and two pointers to left and right child nodes -> Option D

4. Quick Check:

   Binary tree node = data + left + right pointers [OK]

Hint: Remember: binary tree nodes have two child pointers [OK]

Common Mistakes:

• Thinking nodes have no pointers
• Confusing parent pointer with child pointers
• Assuming multiple data fields

2. Which of the following is the correct C syntax to define a binary tree node structure?

easy

A. struct Node { int data; struct Node left; struct Node right; };

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

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

D. struct Node { int data; struct Node* parent; };

Solution

1. Step 1: Check pointer usage in struct

   In C, pointers to the same struct type must be declared with 'struct Node*' inside the struct.

2. Step 2: Identify correct syntax

   struct Node { int data; struct Node* left; struct Node* right; }; correctly uses 'struct Node*' for left and right child pointers.

3. Final Answer:

   struct Node { int data; struct Node* left; struct Node* right; }; -> Option C

4. Quick Check:

   Use 'struct Node*' for pointers inside struct [OK]

Hint: Use 'struct Node*' for pointers inside struct in C [OK]

Common Mistakes:

• Omitting 'struct' keyword before Node*
• Using struct Node instead of pointer causing infinite size
• Confusing parent pointer with child pointers

3. Given the following code, what will be printed?

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

int main() {
  struct Node n1 = {10, NULL, NULL};
  struct Node n2 = {20, NULL, NULL};
  struct Node root = {5, &n1, &n2};
  printf("%d %d %d", root.data, root.left->data, root.right->data);
  return 0;
}

medium

A. 5 10 20

B. 10 5 20

C. 5 0 0

D. Compilation error

Solution

1. Step 1: Understand node initialization

   n1 has data 10, n2 has data 20, root has data 5 with left pointing to n1 and right pointing to n2.

2. Step 2: Trace printf output

   root.data is 5, root.left->data is 10, root.right->data is 20, so output is '5 10 20'.

3. Final Answer:

   5 10 20 -> Option A

4. Quick Check:

   Print root and children data = 5 10 20 [OK]

Hint: Follow pointers to child nodes for data [OK]

Common Mistakes:

• Confusing data values of nodes
• Assuming NULL pointers print zero
• Mixing order of print arguments

4. Identify the error in this binary tree node definition:

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

medium

A. Left and right should be pointers, not structs

B. Missing semicolon after struct definition

C. Data field should be a pointer

D. Struct name should be lowercase

Solution

1. Step 1: Analyze struct member types

   Left and right are declared as struct Node, which causes infinite size because each contains two more structs recursively.

2. Step 2: Correct pointer usage

   They should be pointers (struct Node*) to avoid infinite recursion and allow linking nodes.

3. Final Answer:

   Left and right should be pointers, not structs -> Option A

4. Quick Check:

   Child nodes must be pointers to avoid infinite size [OK]

Hint: Use pointers for child nodes to prevent infinite size [OK]

Common Mistakes:

• Declaring child nodes as structs instead of pointers
• Ignoring compiler errors about struct size
• Thinking data field needs to be pointer

5. You want to create a binary tree node in C that stores a character and has pointers to left and right children. Which of the following struct definitions correctly achieves this and allows dynamic node creation?

hard

A. struct Node { char data; struct Node left; struct Node right; }; struct Node* createNode(char c) { struct Node newNode; newNode.data = c; newNode.left = NULL; newNode.right = NULL; return &newNode; }

B. struct Node { char data; struct Node* left; struct Node* right; }; struct Node* createNode(char c) { struct Node* newNode = malloc(sizeof(struct Node)); newNode->data = c; newNode->left = NULL; newNode->right = NULL; return newNode; }

C. struct Node { char data; struct Node* left; struct Node* right; }; struct Node createNode(char c) { struct Node newNode; newNode.data = c; newNode.left = NULL; newNode.right = NULL; return newNode; }

D. struct Node { char data; struct Node* left; struct Node* right; }; struct Node* createNode(char c) { struct Node newNode; newNode.data = c; newNode.left = NULL; newNode.right = NULL; return newNode; }

Solution

1. Step 1: Check struct definition

   struct Node { char data; struct Node* left; struct Node* right; }; struct Node* createNode(char c) { struct Node* newNode = malloc(sizeof(struct Node)); newNode->data = c; newNode->left = NULL; newNode->right = NULL; return newNode; } correctly defines pointers for left and right children and uses char data type.

2. Step 2: Verify dynamic node creation

   struct Node { char data; struct Node* left; struct Node* right; }; struct Node* createNode(char c) { struct Node* newNode = malloc(sizeof(struct Node)); newNode->data = c; newNode->left = NULL; newNode->right = NULL; return newNode; } uses malloc to allocate memory dynamically and initializes pointers to NULL, returning a pointer to the new node.

3. Final Answer:

   Correct struct with pointers and dynamic allocation using malloc -> Option B

4. Quick Check:

   Dynamic node creation requires malloc and pointer returns [OK]

Hint: Use malloc and pointers for dynamic binary tree nodes [OK]

Common Mistakes:

• Returning address of local variable (invalid after function ends)
• Using struct members instead of pointers for children
• Not initializing child pointers to NULL