Binary Tree Node Structure in DSA C

Mental Model

A binary tree node holds a value and links to two child nodes, left and right, which can be empty.

Analogy: Think of a family tree where each person can have up to two children, one on the left side and one on the right side.

    [Node]
    /    \
[Left]  [Right]
   null    null

Dry Run Walkthrough

Input: Create a binary tree node with value 5, left child 3, and right child 7

Goal: Build a binary tree node that connects to two child nodes correctly

Step 1: Create root node with value 5

[5] -> left: null, right: null

Why: Start with the root node which has no children yet

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

[5] -> left: [3], right: null

Why: Attach left child to root to build the left branch

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

[5] -> left: [3], right: [7]

Why: Attach right child to root to build the right branch

Result:

[5] -> left: [3], right: [7]

Annotated Code

DSA C

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

// Define the binary tree node structure
typedef struct Node {
    int value;
    struct Node* left;
    struct Node* right;
} Node;

// Function to create a new node with given value
Node* createNode(int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    newNode->value = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// Function to print the node and its children
void printNode(Node* node) {
    if (node == NULL) {
        printf("null");
        return;
    }
    printf("[%d] -> left: ", node->value);
    if (node->left) {
        printf("[%d]", node->left->value);
    } else {
        printf("null");
    }
    printf(", right: ");
    if (node->right) {
        printf("[%d]", node->right->value);
    } else {
        printf("null");
    }
    printf("\n");
}

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

    // Step 2: Create left child and link
    root->left = createNode(3);

    // Step 3: Create right child and link
    root->right = createNode(7);

    // Print the structure
    printNode(root);

    // Free allocated memory
    free(root->left);
    free(root->right);
    free(root);

    return 0;
}

Node* newNode = (Node*)malloc(sizeof(Node));

allocate memory for a new node

newNode->value = val;

store the given value in the node

newNode->left = NULL; newNode->right = NULL;

initialize left and right child pointers to null

root->left = createNode(3);

link left child node to root

root->right = createNode(7);

link right child node to root

printNode(root);

display the root node and its children

Output

[5] -> left: [3], right: [7]

Complexity Analysis

Time: O(1) because creating and linking a single node takes constant time

Space: O(1) because only a fixed number of nodes are created

vs Alternative: Compared to arrays, binary tree nodes use pointers to link children dynamically without fixed size

Edge Cases

Creating a node with no children

Node's left and right pointers are set to null

DSA C

newNode->left = NULL; newNode->right = NULL;

Creating a node with only one child

One child pointer is set to a node, the other remains null

DSA C

root->left = createNode(3); // right remains null if not set

When to Use This Pattern

When you need to represent hierarchical data with up to two branches per item, use binary tree nodes because they link data with left and right pointers.

Common Mistakes

Mistake: Forgetting to initialize left and right pointers to null
Fix: Always set left and right pointers to NULL when creating a new node

Mistake: Not allocating memory before using a node
Fix: Use malloc to allocate memory before assigning values

Summary

It defines a node that holds a value and links to two child nodes in a binary tree.

Use it when building binary trees to connect nodes with left and right children.

Remember each node has exactly two pointers for children, which can be null if no child exists.

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