Create a Binary Tree Manually in DSA Java - 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, we want to understand how the time it takes grows as we add more nodes.

We ask: How does the work increase when the tree gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Node {
    int value;
    Node left, right;
    Node(int val) { value = val; left = right = null; }
}

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 assigning nodes directly to left and right children.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Creating and linking nodes manually without loops or recursion.
• How many times: Each node is created and linked once, no repetition.

How Execution Grows With Input

Since each node is created and linked one time, the work grows 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 increases in a straight line as the number of nodes increases.

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 constant time because we just write code once."

[OK] Correct: Even though the code is written once, each node creation and linking is a separate step that takes time, so the total time grows with the number of nodes.

Interview Connect

Understanding how manual tree creation scales helps you reason about building trees in code and prepares you to analyze more complex tree operations.

Self-Check

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

Practice

1. What is the correct way to create a root node of a binary tree manually in Java using a Node class with an integer value?

easy

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

B. Node root = Node(10);

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

D. Node root = new Node(10);

Solution

1. Step 1: Understand Node object creation

   In Java, to create an object, you use the new keyword followed by the constructor call.

2. Step 2: Apply correct syntax for constructor with value

   The constructor Node(10) creates a node with value 10. So new Node(10) is correct.

3. Final Answer:

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

4. Quick Check:

   Object creation with constructor = new Node(10) [OK]

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

Common Mistakes:

• Omitting 'new' keyword
• Using incorrect constructor syntax
• Trying to assign value without constructor

2. Which of the following is the correct syntax to manually link a left child node with value 5 to a root node in Java?

easy

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

B. root.leftNode = new Node(5);

C. root.left = Node(5);

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

Solution

1. Step 1: Understand node linking in binary tree

   The left child of a node is usually accessed by left field. Assigning a new node requires new Node(value).

2. Step 2: Apply correct field and constructor syntax

   So root.left = new Node(5); correctly creates and links the left child.

3. Final Answer:

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

4. Quick Check:

   Link left child with new Node = root.left = new Node(5) [OK]

Hint: Use 'root.left = new Node(value)' to link left child [OK]

Common Mistakes:

• Using wrong field name like leftNode
• Omitting 'new' keyword
• Incorrect constructor call without 'new'

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

class Node {
  int value;
  Node left, right;
  Node(int v) { value = v; }
}

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);

void inorder(Node node) {
  if (node == null) return;
  inorder(node.left);
  System.out.print(node.value + " ");
  inorder(node.right);
}

inorder(root);

medium

A. 4 2 5 1 3

B. 1 2 3 4 5

C. 1 3 2 4 5

D. 2 4 5 1 3

Solution

1. Step 1: Understand inorder traversal order

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

2. Step 2: Trace traversal on given tree

   Left subtree of root(1) is node(2) with children 4 and 5.
   Traverse left subtree of 2: 4 (no children)
   Visit 2
   Traverse right subtree of 2: 5 (no children)
   Visit root 1
   Traverse right subtree of root: 3 (no children)
   Sequence: 4 2 5 1 3

3. Final Answer:

   4 2 5 1 3 -> Option A

4. Quick Check:

   Inorder = left, root, right = 4 2 5 1 3 [OK]

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

Common Mistakes:

• Confusing preorder or postorder with inorder
• Missing left or right subtree nodes
• Printing root before left subtree

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

class Node {
  int value;
  Node left, right;
  Node(int v) { value = v; }
}

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

medium

A. Node class constructor is missing

B. Cannot assign right child after root creation

C. Missing 'new' keyword when creating left child node

D. Value type should be String, not int

Solution

1. Step 1: Check node creation syntax

   Creating a new node requires the 'new' keyword before constructor call.

2. Step 2: Identify incorrect line

   Line root.left = Node(5); misses 'new' keyword, causing syntax error.

3. Final Answer:

   Missing 'new' keyword when creating left child node -> Option C

4. Quick Check:

   Object creation needs 'new' keyword [OK]

Hint: Always use 'new' to create objects in Java [OK]

Common Mistakes:

• Omitting 'new' keyword
• Confusing constructor call with method call
• Assuming automatic object creation

5. You want to manually create a binary tree with root value 7, left child 3, right child 9, and left child's right child 5. Which code snippet correctly builds this tree?

hard

A. Node root = new Node(7);
root.left = new Node(3);
root.right = new Node(9);
root.right.left = new Node(5);

B. Node root = new Node(7);
root.left = new Node(3);
root.right = new Node(9);
root.left.right = new Node(5);

C. Node root = new Node(7);
root.left = new Node(3);
root.left.left = new Node(9);
root.left.right = new Node(5);

D. Node root = new Node(7);
root.right = new Node(3);
root.left = new Node(9);
root.left.right = new Node(5);

Solution

1. Step 1: Create root and direct children

   Root is 7, left child 3, right child 9, so assign accordingly.

2. Step 2: Add left child's right child

   Left child's right child is 5, so root.left.right = new Node(5); is correct.

3. Final Answer:

   Node root = new Node(7); root.left = new Node(3); root.right = new Node(9); root.left.right = new Node(5); -> Option B

4. Quick Check:

   Assign children correctly by following tree structure [OK]

Hint: Assign children stepwise matching tree structure [OK]

Common Mistakes:

• Swapping left and right children
• Assigning child to wrong parent node
• Missing intermediate child nodes