Binary Tree Node Structure in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Traversal on a Simple Binary Tree

What is the output of the inorder traversal for the given binary tree?

DSA C++

#include <iostream>
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    inorder(root);
    return 0;
}

A 5 10 15

B 15 10 5

C 10 5 15

D 10 15 5

💡 Hint

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

Inorder traversal prints nodes in ascending order for binary search trees. Here, left child 5 is printed first, then root 10, then right child 15.

❓ Predict Output

intermediate

Output of Preorder Traversal on a Binary Tree

What is the output of the preorder traversal for the given binary tree?

DSA C++

#include <iostream>
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

int main() {
    Node* root = new Node(20);
    root->left = new Node(10);
    root->right = new Node(30);
    preorder(root);
    return 0;
}

A 20 10 30

B 20 30 10

C 30 20 10

D 10 20 30

💡 Hint

Preorder traversal visits node first, then left child, then right child.

Preorder traversal prints root first, then left subtree, then right subtree. So output is '20 10 30 '.

❓ Predict Output

advanced

Output of Postorder Traversal on a Binary Tree

What is the output of the postorder traversal for the given binary tree?

DSA C++

#include <iostream>
struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

int main() {
    Node* root = new Node(7);
    root->left = new Node(3);
    root->right = new Node(9);
    postorder(root);
    return 0;
}

A 3 7 9

B 7 3 9

C 9 7 3

D 3 9 7

💡 Hint

Postorder traversal visits left child, right child, then node.

Postorder traversal prints left subtree, right subtree, then root. So output is '3 9 7 '.

❓ Predict Output

advanced

Output of Level Order Traversal on a Binary Tree

What is the output of the level order traversal (breadth-first) for the given binary tree?

DSA C++

#include <iostream>
#include <queue>

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

void levelOrder(Node* root) {
    if (!root) return;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();
        std::cout << curr->data << " ";
        if (curr->left) q.push(curr->left);
        if (curr->right) q.push(curr->right);
    }
}

int main() {
    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);
    levelOrder(root);
    return 0;
}

A 1 3 2 5 4

B 4 5 2 3 1

C 1 2 3 4 5

D 2 1 3 4 5

💡 Hint

Level order visits nodes level by level from left to right.

Level order traversal prints nodes level-wise: root first, then children from left to right. Output is '1 2 3 4 5 '.

🧠 Conceptual

expert

Number of Nodes in a Complete Binary Tree of Height h

What is the maximum number of nodes in a complete binary tree of height h (where height is the number of edges from root to deepest leaf)?

A 2^(h+1)

B 2^(h+1) - 1

C 2^h - 1

D 2^h

💡 Hint

A complete binary tree is full except possibly the last level, which is filled from left to right.

A complete binary tree of height h has at most 2^(h+1) - 1 nodes because each level i has up to 2^i nodes, summing to this formula.

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