Binary Tree Node Structure in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to declare the data member for storing the node's value.

DSA C++

struct Node {
    int [1];
    Node* left;
    Node* right;
};

Drag options to blanks, or click blank then click option'

Avalue

Bnode

CdataValue

DvalNode

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'node' which is confusing as it suggests the whole node, not just the value.

Using overly long or unclear names like 'dataValue' or 'valNode'.

The data member to store the node's value is commonly named 'value'.

2fill in blank

medium

Complete the code to initialize the left child pointer to nullptr in the constructor.

DSA C++

struct Node {
    int value;
    Node* left;
    Node* right;

    Node(int val) : value(val), [1](nullptr), right(nullptr) {}
};

Drag options to blanks, or click blank then click option'

Aright

Bvalue

Cleft

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing the wrong pointer like 'right' instead of 'left'.

Trying to initialize 'value' again which is already initialized.

The left child pointer is initialized to nullptr using 'left(nullptr)'.

3fill in blank

hard

Fix the error in the constructor initializer list to correctly initialize the right child pointer.

DSA C++

struct Node {
    int value;
    Node* left;
    Node* right;

    Node(int val) : value(val), left(nullptr), [1](nullptr) {}
};

Drag options to blanks, or click blank then click option'

Aleft

Bnode

Cvalue

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing 'left' twice instead of 'right'.

Trying to initialize 'value' again which is already done.

The right child pointer should be initialized as 'right(nullptr)' in the initializer list.

4fill in blank

hard

Fill both blanks to complete the function that checks if a node is a leaf (no children).

DSA C++

bool isLeaf(Node* node) {
    return node->[1] == nullptr && node->[2] == nullptr;
}

Drag options to blanks, or click blank then click option'

Aleft

Bright

Cvalue

Dnode

Attempts:

3 left

💡 Hint

Common Mistakes

Checking 'value' or 'node' instead of child pointers.

Checking only one child pointer instead of both.

A leaf node has both left and right pointers set to nullptr.

5fill in blank

hard

Fill all three blanks to complete the function that creates a new node with given value and returns its pointer.

DSA C++

Node* createNode(int val) {
    Node* newNode = new Node([1]);
    newNode->[2] = nullptr;
    newNode->[3] = nullptr;
    return newNode;
}

Drag options to blanks, or click blank then click option'

Aval

Bleft

Cright

Dvalue

Attempts:

3 left

💡 Hint

Common Mistakes

Passing 'value' instead of 'val' to constructor.

Setting wrong members like 'value' instead of child pointers.

Forgetting to initialize one of the child pointers.

The constructor is called with 'val', and both child pointers 'left' and 'right' are set to nullptr.

Practice

1. What does a typical binary tree node structure contain in C++?

easy

A. A data value and pointers to left and right child nodes

B. Only a data value without any pointers

C. Pointers to parent and sibling nodes only

D. A data value and a pointer to the next node in a list

Solution

1. Step 1: Understand binary tree node components

   A binary tree node stores a data value and has two pointers: one to the left child and one to the right child.

2. Step 2: Compare options with definition

   A data value and pointers to left and right child nodes correctly describes this structure. Other options miss pointers or mention unrelated pointers.

3. Final Answer:

   A data value and pointers to left and right child nodes -> Option A

4. Quick Check:

   Binary tree node = data + left + right pointers [OK]

Hint: Remember: binary tree nodes have two child pointers [OK]

Common Mistakes:

• Thinking nodes have only one pointer
• Confusing with linked list node structure
• Assuming parent pointer is always present

2. Which of the following is the correct syntax to define a binary tree node struct in C++?

easy

A. struct Node { int data; Node* left; Node* right; };

B. struct Node { int data; Node left; Node right; };

C. struct Node { int data; Node& left; Node& right; };

D. struct Node { int data; Node left*; Node right*; };

Solution

1. Step 1: Check pointer syntax in struct

   In C++, pointers are declared with '*', so left and right children must be pointers: Node* left; Node* right;

2. Step 2: Validate each option

   struct Node { int data; Node* left; Node* right; }; uses correct pointer syntax. struct Node { int data; Node left; Node right; }; uses objects (causes infinite recursion). struct Node { int data; Node& left; Node& right; }; uses references incorrectly. struct Node { int data; Node left*; Node right*; }; has invalid pointer syntax.

3. Final Answer:

   struct Node { int data; Node* left; Node* right; }; -> Option A

4. Quick Check:

   Pointer syntax = Node* left/right [OK]

Hint: Pointers use * after type, not before variable name [OK]

Common Mistakes:

• Using objects instead of pointers for children
• Using references (&) for child nodes
• Incorrect pointer syntax like 'left*'

3. What will be the output of the following code snippet?

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

int main() {
  Node* root = new Node(10);
  root->left = new Node(5);
  root->right = new Node(15);
  std::cout << root->left->data << " " << root->right->data << std::endl;
  return 0;
}

medium

A. Compilation error

B. 5 15

C. 5 10

D. 10 15

Solution

1. Step 1: Understand node creation and assignments

   Root node has data 10. Left child is assigned a node with data 5. Right child is assigned a node with data 15.

2. Step 2: Trace the output statement

   Output prints root->left->data (5) and root->right->data (15) separated by space.

3. Final Answer:

   5 15 -> Option B

4. Quick Check:

   Left child = 5, Right child = 15 [OK]

Hint: Follow pointer assignments to print child node data [OK]

Common Mistakes:

• Printing root data instead of children
• Confusing left and right child values
• Forgetting to initialize children

4. Identify the error in the following binary tree node struct and fix it:

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

medium

A. Remove constructor and use public members only

B. Add default constructor to initialize data

C. Change 'int data;' to 'int* data;'

D. Change 'Node left;' and 'Node right;' to 'Node* left;' and 'Node* right;'

Solution

1. Step 1: Identify the problem with member declarations

   Declaring 'Node left;' and 'Node right;' causes infinite recursion because each Node contains two Nodes inside it.

2. Step 2: Fix by using pointers for children

   Change to 'Node* left;' and 'Node* right;' to hold addresses of child nodes, avoiding infinite size.

3. Final Answer:

   Change 'Node left;' and 'Node right;' to 'Node* left;' and 'Node* right;' -> Option D

4. Quick Check:

   Child nodes must be pointers to avoid infinite recursion [OK]

Hint: Child nodes must be pointers, not objects [OK]

Common Mistakes:

• Using objects for children causing infinite size
• Ignoring pointer usage in tree nodes
• Trying to fix with constructors only

5. You want to create a binary tree node struct that also stores a pointer to its parent node. Which of the following is the correct way to define it?

hard

A. struct Node { int data; Node left; Node right; Node parent; Node(int val) : data(val) {} };

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

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

D. struct Node { int data; Node* left; Node* right; Node& parent; Node(int val) : data(val), left(nullptr), right(nullptr), parent(*this) {} };

Solution

1. Step 1: Understand parent pointer type

   The parent pointer must be of type 'Node*' to point to another node or nullptr if no parent.

2. Step 2: Check constructor initialization

   Constructor initializes data and sets left, right, and parent pointers to nullptr correctly.

3. Step 3: Validate options

   struct Node { int data; Node* left; Node* right; Node* parent; Node(int val) : data(val), left(nullptr), right(nullptr), parent(nullptr) {} }; correctly uses pointers for children and parent. struct Node { int data; Node left; Node right; Node parent; Node(int val) : data(val) {} }; uses objects causing recursion. struct Node { int data; Node* left; Node* right; int* parent; Node(int val) : data(val), left(nullptr), right(nullptr), parent(nullptr) {} }; wrongly uses 'int*' for parent. struct Node { int data; Node* left; Node* right; Node& parent; Node(int val) : data(val), left(nullptr), right(nullptr), parent(*this) {} }; uses reference incorrectly and initializes parent to self.

4. Final Answer:

   struct Node { int data; Node* left; Node* right; Node* parent; Node(int val) : data(val), left(nullptr), right(nullptr), parent(nullptr) {} }; -> Option C

5. Quick Check:

   Parent pointer = Node* parent [OK]

Hint: Parent pointer must be Node* and initialized to nullptr [OK]

Common Mistakes:

• Using object or reference for parent pointer
• Incorrect pointer type for parent
• Initializing parent pointer incorrectly