Create a Binary Tree Manually in DSA Python - Execution Trace

Concept Flow - Create a Binary Tree Manually

Create root node

↓

Assign left child to root

↓

Assign right child to root

↓

Assign children to left child

↓

Assign children to right child

↓

Tree fully constructed

Start by creating the root node, then assign left and right children step-by-step until the tree is complete.

Execution Sample

DSA Python

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

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

This code creates a root node with value 1 and assigns two children with values 2 and 3.

Execution Table

Step	Operation	Node Created/Assigned	Pointer Changes	Visual State
1	Create root node	Node(1)	root -> Node(1)	1
2	Assign left child to root	Node(2)	root.left -> Node(2)	1 / 2
3	Assign right child to root	Node(3)	root.right -> Node(3)	1 / \ 2 3
4	Assign left child to root.left	Node(4)	root.left.left -> Node(4)	1 / \ 2 3 /
5	Assign right child to root.left	Node(5)	root.left.right -> Node(5)	1 / \ 2 3 / \ 4 5
6	Assign left child to root.right	Node(6)	root.right.left -> Node(6)	1 / \ 2 3 / \ / 4 5 6
7	Assign right child to root.right	Node(7)	root.right.right -> Node(7)	1 / \ 2 3 / \ / \ 4 5 6 7
8	Tree construction complete	None	No pointer changes	1 / \ 2 3 / \ / \ 4 5 6 7

💡 All nodes assigned, tree fully constructed

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
root	None	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)	Node(1)
root.left	None	None	Node(2)	Node(2)	Node(2)	Node(2)	Node(2)	Node(2)	Node(2)
root.right	None	None	None	Node(3)	Node(3)	Node(3)	Node(3)	Node(3)	Node(3)
root.left.left	None	None	None	None	Node(4)	Node(4)	Node(4)	Node(4)	Node(4)
root.left.right	None	None	None	None	None	Node(5)	Node(5)	Node(5)	Node(5)
root.right.left	None	None	None	None	None	None	Node(6)	Node(6)	Node(6)
root.right.right	None	None	None	None	None	None	None	Node(7)	Node(7)

Key Moments - 3 Insights

Why do we assign children using root.left and root.right instead of creating new nodes separately?

Because assigning children directly to root.left and root.right links the new nodes to the tree structure, as shown in steps 2 and 3 of the execution_table where pointers root.left and root.right are updated.

What happens if we forget to assign a child node to left or right?

The child pointer remains None, meaning that branch of the tree ends there. For example, before step 4, root.left.left is None, so no further nodes exist on that side.

How does the visual state represent the tree structure after each step?

The visual state shows the tree growing by adding nodes as branches. For example, after step 3, the root has two children 2 and 3, visually represented as '1' with '2' and '3' below it connected by lines.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, which node is assigned as root.left.right?

A Node(6)

B Node(4)

C Node(5)

D Node(7)

💡 Hint

Check the 'Node Created/Assigned' column at step 5 in the execution_table.

At which step does root.right.left get assigned a node?

A Step 4

B Step 6

C Step 5

D Step 7

💡 Hint

Look at the 'Pointer Changes' column for root.right.left in the execution_table.

If we skip step 3, what would be the visual state after step 2?

A 1 with left child 2 only

B 1 with right child 3 only

C 1 with children 2 and 3

D Only node 1

💡 Hint

Refer to the visual state column after step 2 and consider that step 3 assigns the right child.

Concept Snapshot

Create nodes manually by:
- Creating root node
- Assigning left and right children
- Repeat for each child node
Use node.left and node.right pointers
Visualize tree growing step-by-step

Full Transcript

To create a binary tree manually, start by making the root node. Then assign its left and right children by creating new nodes and linking them using the left and right pointers. Continue assigning children to these nodes as needed. Each step updates pointers and grows the tree structure. The visual state after each step shows how the tree looks, helping understand the connections. This method builds the tree from the top down, linking nodes explicitly.

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