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

Time Complexity: Create a Binary Tree Manually

O(n)

Understanding Time Complexity

When we create a binary tree manually, we add nodes one by one. Understanding how long this takes helps us plan for bigger trees.

We want to know: how does the time to build the tree grow as we add more nodes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

This code creates a binary tree by manually linking nodes to form a small tree.

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 fixed amount of work to create and link.

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 directly with the number of nodes added.

Final Time Complexity

Time Complexity: O(n)

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

Common Mistake

[X] Wrong: "Creating a tree manually is instant no matter how big it is."

[OK] Correct: Each node takes time to create and link, so bigger trees take more time.

Interview Connect

Knowing how manual tree creation scales helps you understand more complex tree operations and their costs.

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 a simple class with attributes data, left, and right?

easy

A. root = Node(10) # creates root with data 10 and no children

B. root = Node() # creates root with no data

C. root = Node.left(10) # creates left child with data 10

D. root = Node.right(10) # creates right child with data 10

Solution

1. Step 1: Understand Node class constructor

   The Node class constructor takes data as an argument and initializes left and right children as None.

2. Step 2: Create root node with data

   Using root = Node(10) creates a root node with data 10 and no children.

3. Final Answer:

   root = Node(10) # creates root with data 10 and no children -> Option A

4. Quick Check:

   Create root node with data = root = Node(10) [OK]

Hint: Use Node(data) to create a node with data and empty children [OK]

Common Mistakes:

• Trying to create children directly without root
• Calling left or right as methods
• Creating node without data when constructor requires it

2. Which of the following code snippets correctly assigns a left child node with data 5 to an existing root node named root?

easy

A. root.left = 5

B. root.left(5)

C. root.left.data = 5

D. root.left = Node(5)

Solution

1. Step 1: Assign a new Node object to root.left

   To add a left child, assign a new Node instance with data 5 to root.left.

2. Step 2: Check syntax correctness

   root.left = Node(5) correctly creates and assigns the left child node.

3. Final Answer:

   root.left = Node(5) -> Option D

4. Quick Check:

   Assign left child node = root.left = Node(5) [OK]

Hint: Assign Node(data) to left or right attribute to add child [OK]

Common Mistakes:

• Calling left as a function instead of assigning
• Assigning data directly without creating Node
• Assigning integer directly to left attribute

3. Given the following code, what is the printed output representing the tree structure?

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def print_tree(node):
    if node is None:
        return "null"
    left_str = print_tree(node.left)
    right_str = print_tree(node.right)
    return f"{node.data} -> {left_str} -> {right_str}"

root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
print(print_tree(root))

medium

A. 1 -> 2 -> 4 -> null -> null -> 3 -> null -> null

B. 1 -> 2 -> 4 -> null -> null -> null -> 3 -> null -> null

C. 1 -> 2 -> null -> 4 -> null -> null -> 3 -> null -> null

D. 1 -> 2 -> 4 -> null -> null -> null -> 3 -> null

Solution

1. Step 1: Trace print_tree calls recursively

   Starting at root (1), print left subtree (2) then right subtree (3). Node 2 has left child 4 and no right child. Node 4 has no children.

2. Step 2: Build output string step-by-step

   Node 4 returns "4 -> null -> null". Node 2 returns "2 -> 4 -> null -> null -> null". Node 3 returns "3 -> null -> null". Root returns "1 -> 2 -> 4 -> null -> null -> null -> 3 -> null -> null".

3. Final Answer:

   1 -> 2 -> 4 -> null -> null -> null -> 3 -> null -> null -> Option B

4. Quick Check:

   Recursive print_tree output = 1 -> 2 -> 4 -> null -> null -> null -> 3 -> null -> null [OK]

Hint: Trace recursion left-right-null to build output string [OK]

Common Mistakes:

• Missing null for empty children
• Confusing order of left and right
• Skipping nodes with no children

4. The following code attempts to create a binary tree but throws an error. What is the error and how to fix it?

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = 3  # Error here

medium

A. root.left.left should be root.left.right

B. Missing parentheses when creating Node for left child

C. Assigning integer 3 directly to left child instead of Node object

D. Node class missing __str__ method

Solution

1. Step 1: Identify the error in assignment

   Assigning 3 directly to root.left.left is wrong because it expects a Node object, not an integer.

2. Step 2: Fix by creating a Node object for left child

   Replace root.left.left = 3 with root.left.left = Node(3) to create a proper child node.

3. Final Answer:

   Assigning integer 3 directly to left child instead of Node object -> Option C

4. Quick Check:

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

Hint: Always assign Node(data) to left/right, not raw values [OK]

Common Mistakes:

• Assigning raw data instead of Node instance
• Confusing left and right child assignments
• Ignoring error messages about attribute access

5. You want to manually create this binary tree:

      10
     /  \
    5    15
     \     \
      7     20

Which code snippet correctly creates this tree?

hard

A. root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.right = Node(7)
root.right.right = Node(20)

B. root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.left = Node(7)
root.right.left = Node(20)

C. root = Node(10)
root.left = Node(7)
root.right = Node(5)
root.left.right = Node(20)
root.right.right = Node(15)

D. root = Node(10)
root.left = Node(5)
root.right = Node(15)
root.left.right = Node(20)
root.right.right = Node(7)

Solution

1. Step 1: Create root and immediate children

   Root is 10, left child 5, right child 15.

2. Step 2: Add right child 7 to left node and right child 20 to right node

   Node 5 has right child 7, node 15 has right child 20.

3. Step 3: Verify tree matches diagram

   root = Node(10) root.left = Node(5) root.right = Node(15) root.left.right = Node(7) root.right.right = Node(20) matches the structure exactly with correct child assignments.

4. Final Answer:

   Code in Option A correctly creates the tree -> Option A

5. Quick Check:

   Assign children as per diagram: left.right=7, right.right=20 [OK]

Hint: Match tree diagram child positions carefully when assigning nodes [OK]

Common Mistakes:

• Assigning children to wrong side (left vs right)
• Swapping node data values
• Missing intermediate child nodes