Create a Binary Tree Manually in DSA C++ - Time & Space Complexity

Time Complexity: Create a Binary Tree Manually

O(n)

Understanding Time Complexity

When we create a binary tree manually by adding nodes one by one, it is important to understand how the time taken grows as we add more nodes.

We want to know how the work increases when the tree gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);
    

This code manually creates a binary tree by creating nodes and linking them as left and right children.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Creating and linking each node manually.
• How many times: Once per node added; no loops or recursion here.

How Execution Grows With Input

Each node creation is a separate step. As you add more nodes, the total steps increase directly with the number of nodes.

Input Size (n)	Approx. Operations
10	10 node creations and links
100	100 node creations and links
1000	1000 node creations and links

Pattern observation: The work grows in a straight line with the number of nodes added.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the tree grows directly with the number of nodes you add.

Common Mistake

[X] Wrong: "Creating a binary tree manually is always very slow because it involves complex operations like searching or balancing."

[OK] Correct: When you create nodes manually and link them directly, each step is simple and done once per node, so it grows linearly, not slower.

Interview Connect

Understanding how manual tree creation scales helps you explain basic data structure setup clearly and confidently in interviews.

Self-Check

"What if we created the tree by inserting nodes one by one using a search to find the correct position? How would the time complexity change?"

Practice

1. What is the correct way to manually create a binary tree node in C++ using a struct named Node with an integer value and two child pointers?

easy

A. Node* root = new Node{10, nullptr, nullptr};

B. Node root = Node(10, nullptr, nullptr);

C. Node root = new Node(10);

D. Node* root = Node(10, nullptr, nullptr);

Solution

1. Step 1: Understand struct initialization with pointers

   To create a node dynamically, use new and initialize with value and nullptr for children.

2. Step 2: Check pointer usage and initialization syntax

   Node* root = new Node{10, nullptr, nullptr}; correctly uses new with brace initialization and sets children to nullptr.

3. Final Answer:

   Node* root = new Node{10, nullptr, nullptr}; -> Option A

4. Quick Check:

   Dynamic node creation with pointers = Node* root = new Node{10, nullptr, nullptr}; [OK]

Hint: Use new with braces and nullptr for children [OK]

Common Mistakes:

• Using new without pointer type
• Not initializing child pointers
• Assigning new Node to non-pointer variable

2. Which of the following code snippets correctly declares a struct for a binary tree node with an integer value and two child pointers in C++?

easy

A. struct Node { int val; Node* left; Node* right; };

B. struct Node { int val; Node left; Node right; };

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

D. struct Node { int val; Node left; Node* right; };

Solution

1. Step 1: Understand struct member types for binary tree

   Child nodes must be pointers to avoid infinite size recursion.

2. Step 2: Check each option for pointer usage

   Only struct Node { int val; Node* left; Node* right; }; uses pointers for both left and right child nodes correctly.

3. Final Answer:

   struct Node { int val; Node* left; Node* right; }; -> Option A

4. Quick Check:

   Child nodes as pointers = struct Node { int val; Node* left; Node* right; }; [OK]

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

Common Mistakes:

• Using struct members as objects instead of pointers
• Mixing pointer and non-pointer types incorrectly
• Forgetting semicolon after struct

3. Given the following code, what is the output of the inorder traversal?

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

Node* root = new Node{1, nullptr, nullptr};
root->left = new Node{2, nullptr, nullptr};
root->right = new Node{3, nullptr, nullptr};

void inorder(Node* node) {
  if (!node) return;
  inorder(node->left);
  std::cout << node->val << " ";
  inorder(node->right);
}

inorder(root);

medium

A. 1 2 3

B. 1 3 2

C. 3 1 2

D. 2 1 3

Solution

1. Step 1: Understand inorder traversal order

   Inorder visits left child, then node, then right child.

2. Step 2: Trace traversal on given tree

   Left child 2 printed first, then root 1, then right child 3.

3. Final Answer:

   2 1 3 -> Option D

4. Quick Check:

   Inorder traversal = 2 1 3 [OK]

Hint: Inorder = left, root, right [OK]

Common Mistakes:

• Confusing preorder or postorder with inorder
• Not handling nullptr checks
• Printing node before left subtree

4. Identify the error in the following code that attempts to create a binary tree node and assign children:

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

Node* root = new Node{10, nullptr, nullptr};
root->left = Node{5, nullptr, nullptr};
root->right = new Node{15, nullptr, nullptr};

medium

A. Node struct missing constructor

B. root->right assignment is incorrect; should not use new

C. root->left assignment is incorrect; should use pointer with new

D. root initialization syntax is wrong

Solution

1. Step 1: Check type of root->left and assignment

   root->left is a pointer, but assigned a Node object, not a pointer.

2. Step 2: Correct assignment requires new for pointer

   Must assign root->left = new Node{5, nullptr, nullptr}; to match pointer type.

3. Final Answer:

   root->left assignment is incorrect; should use pointer with new -> Option C

4. Quick Check:

   Pointer assignment needs new = root->left assignment is incorrect; should use pointer with new [OK]

Hint: Assign pointers with new, not direct objects [OK]

Common Mistakes:

• Assigning object to pointer without new
• Confusing pointer and object types
• Missing nullptr initialization

5. You want to manually create a binary tree with root value 5, left child 3, and right child 7. Which code snippet correctly creates this tree and prints the preorder traversal (root, left, right)?

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

void preorder(Node* node) {
  if (!node) return;
  std::cout << node->val << " ";
  preorder(node->left);
  preorder(node->right);
}

// Which code below is correct?

hard

A. Node* root = new Node(5);
root->left = new Node(3);
root->right = new Node(7);
preorder(root);

B. Node* root = new Node{5, nullptr, nullptr};
root->left = new Node{3, nullptr, nullptr};
root->right = new Node{7, nullptr, nullptr};
preorder(root);

C. Node root = {5, nullptr, nullptr};
root.left = {3, nullptr, nullptr};
root.right = {7, nullptr, nullptr};
preorder(&root);

D. Node* root = new Node{5, nullptr, nullptr};
root->left = Node{3, nullptr, nullptr};
root->right = Node{7, nullptr, nullptr};
preorder(root);

Solution

1. Step 1: Check node creation and pointer assignments

   Node* root = new Node{5, nullptr, nullptr}; root->left = new Node{3, nullptr, nullptr}; root->right = new Node{7, nullptr, nullptr}; preorder(root); correctly uses new with brace initialization and assigns pointers for children.

2. Step 2: Verify preorder call and syntax

   preorder(root) passes pointer correctly; printing order matches preorder traversal.

3. Final Answer:

   Node* root = new Node{5, nullptr, nullptr}; root->left = new Node{3, nullptr, nullptr}; root->right = new Node{7, nullptr, nullptr}; preorder(root); -> Option B

4. Quick Check:

   Correct pointer creation and preorder call = Node* root = new Node{5, nullptr, nullptr}; root->left = new Node{3, nullptr, nullptr}; root->right = new Node{7, nullptr, nullptr}; preorder(root); [OK]

Hint: Use new for all nodes and pass root pointer to preorder [OK]

Common Mistakes:

• Assigning objects to pointers without new
• Using incorrect constructor syntax
• Passing object instead of pointer to preorder