Create a Binary Tree Manually in DSA C++ - Build from Scratch

Create a Binary Tree Manually

📖 Scenario: You are building a simple binary tree to represent a family tree. Each node will hold a person's name as a string. You will create the tree manually by linking nodes together.

🎯 Goal: Build a binary tree manually by creating nodes and linking them as left and right children. Then print the tree nodes in preorder traversal.

📋 What You'll Learn

Create a struct called Node with a string data and two Node* pointers called left and right

Create three nodes with data "Grandparent", "Parent", and "Child"

Link the nodes so that Grandparent is the root, Parent is the left child of Grandparent, and Child is the right child of Parent

Write a function void preorder(Node* root) that prints the nodes in preorder (root, left, right)

Call preorder with the root node and print the names separated by spaces

💡 Why This Matters

🌍 Real World

Binary trees are used in many areas like family trees, decision trees, and organizing data hierarchically.

💼 Career

Understanding how to create and traverse trees is fundamental for software development, especially in areas like databases, compilers, and AI.

1

Create the Node struct and three nodes

Create a struct called Node with a string data and two Node* pointers called left and right. Then create three nodes called grandparent, parent, and child with data "Grandparent", "Parent", and "Child" respectively. Initialize their left and right pointers to nullptr.

DSA C++

#include 
#include 

using namespace std;

int main() {

    // Create struct Node and three nodes here

    return 0;
}

Hint

Define the struct outside main(). Initialize pointers to nullptr.

2

Link the nodes to form the tree

Link the nodes so that grandparent.left points to &parent and parent.right points to &child.

DSA C++

#include 
#include 

using namespace std;

struct Node {
    string data;
    Node* left;
    Node* right;
};

int main() {
    Node grandparent = {"Grandparent", nullptr, nullptr};
    Node parent = {"Parent", nullptr, nullptr};
    Node child = {"Child", nullptr, nullptr};

    // Link nodes here

    return 0;
}

Hint

Use the address-of operator & to link nodes.

3

Write a preorder traversal function

Write a function called void preorder(Node* root) that prints the data of the node, then recursively calls itself on the left child, then on the right child. Use cout to print the data followed by a space.

DSA C++

#include 
#include 

using namespace std;

struct Node {
    string data;
    Node* left;
    Node* right;
};

void preorder(Node* root) {
    // Print root data and recursively call preorder on left and right
    // Your code here
}

int main() {
    Node grandparent = {"Grandparent", nullptr, nullptr};
    Node parent = {"Parent", nullptr, nullptr};
    Node child = {"Child", nullptr, nullptr};

    grandparent.left = &parent;
    parent.right = &child;

    return 0;
}

Hint

Check if root is nullptr to stop recursion. Print root->data then call preorder on left and right.

4

Call preorder and print the tree

Call the preorder function with the address of grandparent and print a newline after the traversal.

DSA C++

#include 
#include 

using namespace std;

struct Node {
    string data;
    Node* left;
    Node* right;
};

void preorder(Node* root) {
    if (root == nullptr) return;
    cout data left);
    preorder(root->right);
}

int main() {
    Node grandparent = {"Grandparent", nullptr, nullptr};
    Node parent = {"Parent", nullptr, nullptr};
    Node child = {"Child", nullptr, nullptr};

    grandparent.left = &parent;
    parent.right = &child;

    // Call preorder with &grandparent and print newline
    // Your code here

    return 0;
}

Hint

Call preorder(&grandparent) and then print endl.

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