Create a Binary Tree Manually in DSA C++ - Execution Trace

Concept Flow - Create a Binary Tree Manually

Create root node

↓

Assign root value

↓

Create left child node

↓

Assign left child value

↓

Create right child node

↓

Assign right child value

↓

Repeat for more nodes or stop

Start by creating the root node, then create and assign left and right child nodes step-by-step to build the tree manually.

Execution Sample

DSA C++

struct Node {
  int data;
  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};

This code creates a root node with value 1, then manually adds left and right child nodes with values 2 and 3.

Execution Table

Step	Operation	Node Created	Pointer Changes	Visual State
1	Create root node	Node(1)	root -> Node(1)	1
2	Create left child	Node(2)	root->left -> Node(2)	1 / 2
3	Create right child	Node(3)	root->right -> Node(3)	1 / \ 2 3
4	No more nodes	None	No pointer changes	1 / \ 2 3

💡 All desired nodes created, manual tree construction complete.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
root	nullptr	Node(1)	Node(1)	Node(1)	Node(1)
root->left	nullptr	nullptr	Node(2)	Node(2)	Node(2)
root->right	nullptr	nullptr	nullptr	Node(3)	Node(3)

Key Moments - 3 Insights

Why do we assign nullptr to left and right when creating a node?

Assigning nullptr means the node has no children yet. This is shown in Step 1 where root's left and right are nullptr before adding children.

What happens if we forget to assign root->left or root->right?

The child pointer stays nullptr, so no child node exists there. Execution table Step 2 and 3 show pointer changes that create children.

How does the visual state represent the tree structure?

The visual state shows nodes and their connections. For example, after Step 3, '1' is root with '2' as left child and '3' as right child.

Visual Quiz - 3 Questions

Look at the execution table at Step 2, what is the value of root->left?

A Node(3)

B nullptr

C Node(2)

D Node(1)

💡 Hint

Check the 'Pointer Changes' and 'Variable Tracker' columns for Step 2.

At which step does root->right get assigned a node?

A Step 1

B Step 3

C Step 2

D Step 4

💡 Hint

Look at the 'Pointer Changes' column in the execution table.

If we skip Step 3, what would the final visual state look like?

A 1 with left child 2 only

B 1 with right child 3 only

C 1 with both children 2 and 3

D Only node 1 with no children

💡 Hint

Refer to the 'Visual State' column after Step 2 and Step 3.

Concept Snapshot

Create nodes manually by allocating memory.
Assign data and set left/right pointers to nullptr initially.
Link nodes by setting left and right pointers.
Visualize tree as root with left and right children.
Stop when all nodes are created.

Full Transcript

To create a binary tree manually, start by creating the root node with data and null children pointers. Then create left and right child nodes by allocating new nodes and linking them to the root's left and right pointers. Each node's left and right pointers start as nullptr to indicate no children. The process continues until all desired nodes are linked. The visual state shows the tree growing step-by-step with root and its children. This method builds the tree from the top down by manually assigning pointers.

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