Create a Binary Tree Manually in DSA C++ - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a binary tree?

A binary tree is a structure where each node has at most two children, called left and right child.

beginner

How do you create a node in a binary tree manually?

You create a node by defining a structure or class with data, and pointers to left and right child nodes, then assign values and connect nodes.

beginner

What does 'null' or 'nullptr' mean in a binary tree node?

It means the node does not have a child in that direction (left or right). It marks the end of a branch.

beginner

Why do we connect nodes manually when creating a binary tree?

Connecting nodes manually sets the parent-child relationships, building the tree structure step by step.

beginner

What is the root node in a binary tree?

The root node is the top node of the tree from which all other nodes branch out.

What is the maximum number of children a node can have in a binary tree?

A 2

B 3

C 1

D 4

In a binary tree, each node can have at most two children: left and right.

What does a 'nullptr' pointer in a node represent?

A Node is the root

B Node has two children

C Node has no child in that direction

D Node is a leaf with children

A nullptr means the node does not have a child on that side.

Which node is considered the starting point of a binary tree?

A Leaf node

B Root node

C Left child

D Right child

The root node is the top node from which the tree grows.

When creating a binary tree manually, what must you do after creating nodes?

A Connect nodes by setting left and right pointers

B Delete nodes immediately

C Sort nodes by value

D Convert nodes to arrays

You connect nodes by assigning their left and right pointers to build the tree.

What is the simplest way to represent a node in C++ for a binary tree?

A An integer variable

B A single pointer

C A string variable

D A class or struct with data and two pointers

A node typically has data and two pointers to left and right children.

Explain how to create a binary tree manually in C++.

Think about how you build a family tree by connecting parents and children.

Describe the role of the root node and child nodes in a binary tree.

Imagine a tree trunk (root) and branches (children).

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