Binary Tree Node Structure in DSA C - Time & Space Complexity

Time Complexity: Binary Tree Node Structure

O(1)

Understanding Time Complexity

We want to understand how the time to create or access nodes in a binary tree changes as the tree grows.

How does the number of steps grow when we add more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Define a binary tree node structure
struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

// Create a new node
struct Node* createNode(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
    

This code defines a node and a function to create a new node with given data.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Allocating memory and setting values for one node.
• How many times: Each call creates exactly one node, no loops or recursion here.

How Execution Grows With Input

Each node creation takes a fixed number of steps, no matter how many nodes exist.

Input Size (n)	Approx. Operations
10	10 node creations x fixed steps each
100	100 node creations x fixed steps each
1000	1000 node creations x fixed steps each

Pattern observation: The total work grows directly with the number of nodes created.

Final Time Complexity

Time Complexity: O(1) per node creation

This means creating one node takes the same fixed time, regardless of tree size.

Common Mistake

[X] Wrong: "Creating a node takes longer as the tree grows because the tree is bigger."

[OK] Correct: Creating a node only involves allocating memory and setting values, which does not depend on the tree size.

Interview Connect

Understanding that node creation is a constant-time operation helps you focus on the parts of tree algorithms that actually depend on tree size, like traversals or searches.

Self-Check

"What if the createNode function also inserted the node into a tree by searching for the correct position? How would the time complexity change?"

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