Create a Binary Tree Manually in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Manual Binary Tree Creation and Inorder Traversal

What is the output of the inorder traversal after manually creating this binary tree?

DSA C++

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

Node* root = new Node(10);
root->left = new Node(5);
root->right = new Node(15);
root->left->left = new Node(3);
root->left->right = new Node(7);

void inorder(Node* node) {
    if (!node) return;
    inorder(node->left);
    std::cout << node->data << " ";
    inorder(node->right);
}

inorder(root);

A 15 10 7 5 3

B 10 5 3 7 15

C 3 5 7 10 15

D 5 3 7 10 15

💡 Hint

Inorder traversal visits left subtree, then node, then right subtree.

Inorder traversal visits nodes in ascending order for a binary search tree. The tree nodes are 3, 5, 7, 10, 15 in that order.

🧠 Conceptual

intermediate

Number of Nodes in a Manually Created Binary Tree

If you manually create a binary tree with root node and add two children to the root, and then add one child to the left child, how many nodes does the tree have?

A 4

B 5

C 3

D 2

💡 Hint

Count the root, its two children, and the one child added to the left child.

The tree has 1 root + 2 children + 1 child of left child = 4 nodes total.

🔧 Debug

advanced

Identify the Bug in Manual Binary Tree Node Linking

What error will occur when running this code snippet that manually creates a binary tree?

DSA C++

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

Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->left->right = new Node(5);

// Mistake: Trying to access right child of a nullptr
std::cout << root->right->left->data << std::endl;

A No output, program runs fine

B Compilation error: missing semicolon

C Output: 0

D Segmentation fault (accessing nullptr)

💡 Hint

Check if root->right->left is initialized before accessing.

root->right->left is nullptr because no node was assigned. Accessing its data causes a segmentation fault.

🚀 Application

advanced

Manual Binary Tree Height Calculation

Given a manually created binary tree, what is the height of the tree?

DSA C++

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

Node* root = new Node(8);
root->left = new Node(3);
root->right = new Node(10);
root->left->left = new Node(1);
root->left->right = new Node(6);
root->left->right->left = new Node(4);
root->right->right = new Node(14);
root->right->right->left = new Node(13);

int height(Node* node) {
    if (!node) return 0;
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

int h = height(root);
std::cout << h << std::endl;

A 3

B 4

C 5

D 2

💡 Hint

Height is the longest path from root to leaf node.

The longest path is root(8) -> right(10) -> right(14) -> left(13), which has 4 nodes, so height is 4.

🧠 Conceptual

expert

Number of Null Pointers in a Complete Binary Tree of Height 3

How many null pointers are there in a complete binary tree of height 3 (height counted as number of nodes on longest path from root to leaf)?

A 8

B 7

C 4

D 15

💡 Hint

A complete binary tree of height h has 2^h - 1 nodes. Number of null pointers = number of missing children.

A complete binary tree of height 3 has 7 nodes. Each node has 2 pointers, total 14 pointers. Since 7 nodes have 6 edges, null pointers = 14 - 6 = 8.

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