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 linking nodes one by one, it is important to understand how the time needed 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.

// Create nodes manually
var root = new TreeNode(1);
root.Left = new TreeNode(2);
root.Right = new TreeNode(3);
root.Left.Left = new TreeNode(4);
root.Left.Right = new TreeNode(5);

This code creates a binary tree by manually assigning left and right children to each node.

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 new node requires a single step to create and link it.

Input Size (n)	Approx. Operations
10	10 steps
100	100 steps
1000	1000 steps

Pattern observation: The work grows directly with the number of nodes; doubling nodes doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to create the tree grows linearly with the number of nodes added.

Common Mistake

[X] Wrong: "Creating a binary tree manually is constant time because we just write code once."

[OK] Correct: Each node creation is a separate step, so the total time depends on how many nodes you add, not just the code lines.

Interview Connect

Understanding how manual tree creation scales helps you reason about more complex tree operations and their costs in real problems.

Self-Check

"What if we used a loop to create and link nodes instead of manual assignments? How would the time complexity change?"

Practice

1. What is the correct way to create a root node manually in a binary tree using C#?

easy

A. Node root = new Node(); root = 10;

B. Node root = Node(10);

C. Node root = new Node(); root.value = 10;

D. Node root = new Node(10);

Solution

1. Step 1: Understand Node creation syntax

   In C#, to create an object, use the 'new' keyword followed by the constructor call with parameters.

2. Step 2: Apply correct syntax for root node

   Using 'new Node(10)' correctly creates a node with value 10 assigned.

3. Final Answer:

   Node root = new Node(10); -> Option D

4. Quick Check:

   Use 'new' keyword with constructor to create node [OK]

Hint: Use 'new' keyword with constructor to create nodes [OK]

Common Mistakes:

• Omitting 'new' keyword when creating node
• Assigning value directly to node variable
• Calling constructor without 'new'

2. Which of the following is the correct syntax to assign a left child node with value 5 to a root node named root?

easy

A. root.left = new Node(5);

B. root.left = Node(5);

C. root.left.value = 5;

D. root.left = 5;

Solution

1. Step 1: Understand child node assignment

   Left child must be assigned a new Node object, not just a value.

2. Step 2: Use correct syntax to assign left child

   Assigning 'root.left = new Node(5);' creates a new node with value 5 as left child.

3. Final Answer:

   root.left = new Node(5); -> Option A

4. Quick Check:

   Assign new Node object to left child [OK]

Hint: Assign new Node object, not just value, to child [OK]

Common Mistakes:

• Assigning value directly instead of Node object
• Omitting 'new' keyword
• Trying to assign value to left property directly

3. Given the following code, what is the output of an inorder traversal (left, root, right)?

Node root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.left.left = new Node(3);

medium

A. [10, 5, 3, 15]

B. [3, 5, 10, 15]

C. [5, 3, 10, 15]

D. [3, 10, 5, 15]

Solution

1. Step 1: Understand inorder traversal order

   Inorder visits left subtree, then root, then right subtree.

2. Step 2: Trace traversal on given tree

   Left subtree of root (10) is node 5, which has left child 3. So traversal order is 3, 5, 10, 15.

3. Final Answer:

   [3, 5, 10, 15] -> Option B

4. Quick Check:

   Inorder = left, root, right [OK]

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

Common Mistakes:

• Confusing preorder or postorder with inorder
• Missing leftmost node in traversal
• Listing nodes in insertion order

4. Identify the error in the following code that tries to create a binary tree:

Node root = new Node(20);
root.left = 10;
root.right = new Node(30);

medium

A. Right child node value is incorrect

B. Missing 'new' keyword when creating root node

C. Assigning integer directly to 'left' instead of a Node object

D. Root node value should be a string, not integer

Solution

1. Step 1: Check left child assignment

   Left child must be a Node object, but code assigns integer 10 directly.

2. Step 2: Verify other parts

   Root node and right child are correctly created with 'new Node()'.

3. Final Answer:

   Assigning integer directly to 'left' instead of a Node object -> Option C

4. Quick Check:

   Child nodes must be Node objects [OK]

Hint: Child nodes must be Node objects, not raw values [OK]

Common Mistakes:

• Assigning raw values instead of Node objects
• Forgetting 'new' keyword for node creation
• Confusing node value type requirements

5. You want to manually create this binary tree:

      8
     / \
    3   10
   / \    \
  1   6    14
     / \   /
    4   7 13

Which code snippet correctly creates this tree?

hard

A. Node root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);
root.left.right.left = new Node(4);
root.left.right.right = new Node(7);
root.right.right = new Node(14);
root.right.right.left = new Node(13);

B. Node root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);
root.left.right.left = new Node(7);
root.left.right.right = new Node(4);
root.right.right = new Node(14);
root.right.right.left = new Node(13);

C. Node root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);
root.left.right.left = new Node(4);
root.left.right.right = new Node(7);
root.right.left = new Node(14);
root.right.left.left = new Node(13);

D. Node root = new Node(8);
root.left = new Node(3);
root.right = new Node(10);
root.left.left = new Node(1);
root.left.right = new Node(6);
root.left.right.left = new Node(4);
root.left.right.right = new Node(7);
root.right.right = new Node(13);
root.right.right.left = new Node(14);

Solution

1. Step 1: Map tree structure to code

   Root 8 has left 3 and right 10. Node 3 has children 1 and 6. Node 6 has children 4 and 7. Node 10 has right child 14, which has left child 13.

2. Step 2: Verify code matches tree

   Node root = new Node(8); root.left = new Node(3); root.right = new Node(10); root.left.left = new Node(1); root.left.right = new Node(6); root.left.right.left = new Node(4); root.left.right.right = new Node(7); root.right.right = new Node(14); root.right.right.left = new Node(13); correctly assigns all nodes to their proper left or right children matching the tree diagram.

3. Final Answer:

   Option A code snippet correctly creates the tree -> Option A

4. Quick Check:

   Match tree structure exactly in code [OK]

Hint: Match each node's left/right child exactly as tree diagram [OK]

Common Mistakes:

• Swapping left and right children
• Assigning children to wrong parent nodes
• Mixing up node values in assignments