Binary Tree Node Structure in DSA C++

Mental Model

A binary tree node holds a value and links to up to two child nodes, left and right, forming a branching structure.

Analogy: Think of a family tree where each person can have up to two children, connecting generations in a branching way.

    [root]
    /    \
[left]  [right]

Dry Run Walkthrough

Input: Create a binary tree node with value 10, left child 5, right child 15

Goal: Build a simple binary tree node with two children and show its structure

Step 1: Create root node with value 10

[10] -> left: null, right: null

Why: Start with the root node which holds the main value

Step 2: Create left child node with value 5 and link to root's left

[10] -> left: [5], right: null

Why: Attach left child to root to build left branch

Step 3: Create right child node with value 15 and link to root's right

[10] -> left: [5], right: [15]

Why: Attach right child to root to build right branch

Result:

[10] -> left: [5], right: [15]

Annotated Code

DSA C++

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

int main() {
    TreeNode* root = new TreeNode(10); // create root node
    root->left = new TreeNode(5);      // create and link left child
    root->right = new TreeNode(15);   // create and link right child

    // Print structure
    std::cout << "Root: " << root->val << "\n";
    std::cout << "Left child: " << root->left->val << "\n";
    std::cout << "Right child: " << root->right->val << "\n";

    // Clean up memory
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

TreeNode* root = new TreeNode(10); // create root node

Create root node with value 10

root->left = new TreeNode(5); // create and link left child

Create left child node and link to root's left pointer

root->right = new TreeNode(15); // create and link right child

Create right child node and link to root's right pointer

Output

Root: 10

Left child: 5

Right child: 15

Complexity Analysis

Time: O(1) because creating a single node and linking children takes constant time

Space: O(1) because only a fixed number of nodes are created

vs Alternative: Compared to arrays, nodes allow dynamic branching without fixed size, using pointers for flexible structure

Edge Cases

Creating a node with no children

Node's left and right pointers are null, representing leaf node

DSA C++

TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

Creating a node with only one child

One child pointer is set, the other remains null, allowing partial branches

DSA C++

root->left = new TreeNode(5);      // create and link left child

When to Use This Pattern

When you need to represent hierarchical data with two branches per item, use binary tree nodes to build the structure.

Common Mistakes

Mistake: Forgetting to initialize left and right pointers to null
Fix: Always set left and right to nullptr in the constructor to avoid undefined behavior

Mistake: Not linking child nodes to the parent node
Fix: Assign new child nodes to parent's left or right pointers explicitly

Summary

Defines a node with a value and two pointers to left and right children.

Use when building tree structures where each node can have up to two children.

The key is each node links to its children, forming a branching tree.

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