Create a Binary Tree Manually in DSA C++

Mental Model

A binary tree is a structure where each node has up to two children, called left and right. Creating it manually means linking nodes one by one to form the tree.

Analogy: Think of a family tree where each person can have up to two children. You build the tree by connecting parents to their children step by step.

      [root]
      /    \
  [left]  [right]
   /  \      /  \
null null null null

Dry Run Walkthrough

Input: Create a binary tree with root 1, left child 2, and right child 3

Goal: Build the tree manually by creating nodes and linking them correctly

Step 1: Create root node with value 1

[1] -> left: null, right: null

Why: Start with the root node as the base of the tree

Step 2: Create left child node with value 2 and link to root's left

[1] -> left: [2], right: null
[2] -> left: null, right: null

Why: Attach left child to root to build left subtree

Step 3: Create right child node with value 3 and link to root's right

[1] -> left: [2], right: [3]
[2] -> left: null, right: null
[3] -> left: null, right: null

Why: Attach right child to root to complete the tree

Result:

[1] -> left: [2], right: [3]
[2] -> left: null, right: null
[3] -> left: null, right: null

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Node structure for binary tree
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Function to print tree in preorder for verification
void preorderPrint(Node* root) {
    if (root == nullptr) return;
    cout << root->data << " ";
    preorderPrint(root->left);
    preorderPrint(root->right);
}

int main() {
    // Step 1: Create root node
    Node* root = new Node(1); // root node with value 1

    // Step 2: Create left child and link
    root->left = new Node(2); // left child with value 2

    // Step 3: Create right child and link
    root->right = new Node(3); // right child with value 3

    // Print tree preorder to verify structure
    preorderPrint(root); // Expected output: 1 2 3 
    cout << endl;
    return 0;
}

Node* root = new Node(1); // root node with value 1

Create root node as the starting point of the tree

root->left = new Node(2); // left child with value 2

Create left child and link it to root's left pointer

root->right = new Node(3); // right child with value 3

Create right child and link it to root's right pointer

preorderPrint(root); // Expected output: 1 2 3

Traverse tree preorder to confirm structure

Output

1 2 3 

Complexity Analysis

Time: O(n) because we create and link each node once

Space: O(n) because each node requires memory allocation

vs Alternative: Manual creation is straightforward and efficient compared to building from arrays or other formats which may require extra parsing

Edge Cases

Empty tree (no nodes)

No nodes are created, root is nullptr, printing shows nothing

DSA C++

if (root == nullptr) return;

Single node tree

Only root node exists, left and right are null

DSA C++

Node* root = new Node(1);

When to Use This Pattern

When you need to build a binary tree from scratch or understand its structure, manually creating nodes and linking them is the first step to grasp tree basics.

Common Mistakes

Mistake: Forgetting to initialize left and right pointers to null
Fix: Initialize left and right pointers to nullptr in the node constructor

Mistake: Linking children incorrectly (e.g., assigning left child to right pointer)
Fix: Carefully assign left child to left pointer and right child to right pointer

Summary

Manually create a binary tree by making nodes and linking left and right children.

Use this when you want to build or understand a binary tree structure from the ground up.

The key is to create each node and connect it properly to form the tree shape.

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