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.