How to Implement Binary Tree in C++: Simple Guide

To implement a binary tree in C++, define a Node struct or class with data and pointers to left and right children. Then create functions to insert nodes and traverse the tree, such as in-order traversal, using recursion or loops.

Syntax

A binary tree node typically contains three parts:

• Data: The value stored in the node.
• Left pointer: Points to the left child node.
• Right pointer: Points to the right child node.

In C++, this is usually done with a struct or class that holds these members.

cpp

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

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

Example

This example shows how to create a simple binary tree, insert nodes manually, and print the tree using in-order traversal.

cpp

#include <iostream>
using namespace std;

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

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

void inorderTraversal(Node* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    // Create nodes
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->left->left = new Node(3);
    root->left->right = new Node(7);

    cout << "In-order traversal of binary tree: ";
    inorderTraversal(root);
    cout << endl;

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

    return 0;
}

Output

In-order traversal of binary tree: 3 5 7 10 15 

Common Pitfalls

Common mistakes when implementing binary trees in C++ include:

• Not initializing child pointers to nullptr, which can cause crashes.
• Forgetting to delete allocated nodes, causing memory leaks.
• Incorrect traversal order leading to wrong output.
• Mixing up left and right child pointers.

Always initialize pointers and carefully manage memory.

cpp

/* Wrong: Not initializing pointers */
struct NodeWrong {
    int data;
    NodeWrong* left;  // uninitialized
    NodeWrong* right; // uninitialized
};

/* Right: Initialize pointers in constructor */
struct NodeRight {
    int data;
    NodeRight* left;
    NodeRight* right;
    NodeRight(int val) : data(val), left(nullptr), right(nullptr) {}
};

Quick Reference

Tips for implementing binary trees in C++:

• Use nullptr to mark empty children.
• Use recursion for simple traversal functions.
• Always free memory with delete to avoid leaks.
• Test your tree by printing traversals like in-order, pre-order, and post-order.

Key Takeaways

Define a node struct with data and left/right pointers initialized to nullptr.

Use recursion to traverse the tree easily and clearly.

Always delete dynamically allocated nodes to prevent memory leaks.

Be careful to keep left and right pointers correct to maintain tree structure.

Test your tree implementation with simple insertions and traversals.