Binary Tree Node Structure in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of inserting nodes in a binary tree

What is the printed output of the binary tree after inserting nodes 10, 5, 15 in that order using the given insert function?

DSA C

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

Node* insert(Node* root, int value) {
    if (root == NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }
    return root;
}

void printInOrder(Node* root) {
    if (root == NULL) return;
    printInOrder(root->left);
    printf("%d -> ", root->data);
    printInOrder(root->right);
}

int main() {
    Node* root = NULL;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    printInOrder(root);
    printf("null\n");
    return 0;
}

A 5 -> 10 -> 15 -> null

B 10 -> 5 -> 15 -> null

C null

D 15 -> 10 -> 5 -> null

💡 Hint

In-order traversal prints nodes in ascending order for a binary search tree.

The insert function places 5 to the left of 10 and 15 to the right. In-order traversal visits left subtree, root, then right subtree, so output is 5 -> 10 -> 15 -> null.

🧠 Conceptual

intermediate

Understanding binary tree node pointers

In a binary tree node structure, what do the 'left' and 'right' pointers represent?

A Pointers to the node's parent and sibling nodes

B Pointers to the next and previous nodes in a linked list

C Pointers to the node's left and right child nodes

D Pointers to the node's data and metadata

💡 Hint

Think about how a binary tree branches out from each node.

In a binary tree, each node has up to two children. The 'left' pointer points to the left child node, and the 'right' pointer points to the right child node.

🔧 Debug

advanced

Identify the error in binary tree node initialization

What error will occur when running this code snippet for creating a new binary tree node?

DSA C

#include <stdlib.h>

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

int main() {
    Node* root = createNode(10);
    printf("%d\n", root->data);
    return 0;
}

A Compilation error due to missing #include <stdlib.h>

B Runtime error due to uninitialized pointers

C Compilation error due to missing semicolon after struct definition

D No error, code runs and prints 10

💡 Hint

malloc requires a specific header file to be included.

The code uses malloc but does not include , which declares malloc. This causes a compilation error.

❓ Predict Output

advanced

Output of pre-order traversal on a binary tree

Given the binary tree constructed by inserting 8, 3, 10, 1, 6, 14, what is the output of the pre-order traversal?

DSA C

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

Node* insert(Node* root, int value) {
    if (root == NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = value;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
    if (value < root->data) {
        root->left = insert(root->left, value);
    } else {
        root->right = insert(root->right, value);
    }
    return root;
}

void printPreOrder(Node* root) {
    if (root == NULL) return;
    printf("%d -> ", root->data);
    printPreOrder(root->left);
    printPreOrder(root->right);
}

int main() {
    Node* root = NULL;
    int values[] = {8, 3, 10, 1, 6, 14};
    for (int i = 0; i < 6; i++) {
        root = insert(root, values[i]);
    }
    printPreOrder(root);
    printf("null\n");
    return 0;
}

A 8 -> 3 -> 1 -> 6 -> 10 -> 14 -> null

B 1 -> 3 -> 6 -> 8 -> 10 -> 14 -> null

C 14 -> 10 -> 8 -> 6 -> 3 -> 1 -> null

D 3 -> 1 -> 6 -> 8 -> 10 -> 14 -> null

💡 Hint

Pre-order traversal visits root first, then left subtree, then right subtree.

Pre-order traversal prints nodes in the order: root, left subtree, right subtree. The insertion creates the tree with root 8, left subtree 3->1,6 and right subtree 10->14.

🧠 Conceptual

expert

Maximum nodes in a binary tree of height h

What is the maximum number of nodes in a binary tree of height h (where height is the number of edges on the longest path from root to leaf)?

A 2^h - 1

B 2^(h+1) - 1

C h^2

D h * 2

💡 Hint

Think about a perfect binary tree where every level is fully filled.

A perfect binary tree of height h has 2^(h+1) - 1 nodes because each level i has 2^i nodes, summing from i=0 to h.

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