How to Implement the Binary Tree Data Structure in C++

A binary tree in C++ can be represented by a node struct with a value and two child links. The example below builds a small tree, counts its nodes, measures its height in edges, and prints its values with inorder traversal.

Represent a binary tree with a node struct

A binary tree node has at most two children, conventionally called left and right. A struct is a class type whose members are public by default, which makes it convenient for this small data structure. Each node stores an integer and owns its child nodes through std::unique_ptr; a null pointer marks a missing child link. It does not itself mean that the node is a leaf: a leaf is a node whose two child links are both null.

A full binary tree has either zero or two children at every node. A perfect binary tree is full and has all leaves at the same depth. The sample built below is full, but not complete: its last level has a gap before a later node. These terms describe different shapes and should not be used interchangeably.

Build a small binary tree

The program creates this deterministic shape, with values chosen to make the traversal easy to follow: 8 (left: 3, right: 10 (left: 9, right: 14)).

std::make_unique creates each node and returns an owning pointer. Moving a pointer into a child transfers ownership, so the root owns the entire tree and its nodes are released automatically when the root goes out of scope. This avoids the manual cleanup required by raw allocations with new.

Run this example:

#include <iostream>
#include <memory>

struct BinTreeNode {
    int data;
    std::unique_ptr<BinTreeNode> left;
    std::unique_ptr<BinTreeNode> right;

    explicit BinTreeNode(int value) : data(value) {}
};

int treeSize(const BinTreeNode* node) {
    if (node == nullptr) {
        return 0;
    }
    return 1 + treeSize(node->left.get()) + treeSize(node->right.get());
}

int treeHeight(const BinTreeNode* node) {
    if (node == nullptr) {
        return -1;
    }
    const int leftHeight = treeHeight(node->left.get());
    const int rightHeight = treeHeight(node->right.get());
    return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}

void printData(const BinTreeNode* node) {
    if (node == nullptr) {
        return;
    }
    printData(node->left.get());
    std::cout << node->data << ' ';
    printData(node->right.get());
}

int main() {
    auto root = std::make_unique<BinTreeNode>(8);
    root->left = std::make_unique<BinTreeNode>(3);
    root->right = std::make_unique<BinTreeNode>(10);
    root->right->left = std::make_unique<BinTreeNode>(9);
    root->right->right = std::make_unique<BinTreeNode>(14);

    std::cout << "size = " << treeSize(root.get()) << '\n';
    std::cout << "height = " << treeHeight(root.get()) << '\n';
    std::cout << "inorder = ";
    printData(root.get());
    std::cout << '\n';
}

The functions accept a pointer to a node without taking ownership. Calling them with root.get() gives them access to the tree while the owning unique_ptr remains responsible for its lifetime. The same recursive definitions work for any tree shape.

Count nodes and calculate tree height

treeSize returns zero for a missing subtree. Otherwise, it counts the current node and adds the sizes of both child subtrees. treeHeight returns -1 for a missing subtree, then adds one to the greater child height. With this convention, height counts edges on the longest root-to-leaf path: a leaf has height 0, and the tree above has height 2. Some definitions count nodes instead, making a leaf height 1; choose one convention and use it consistently.

Print nodes with inorder traversal

printData visits the left subtree, prints the current value, and then visits the right subtree. This is inorder traversal; for a binary search tree, it prints values in sorted order, while for a general binary tree it only follows that traversal order. See the inorder traversal guide for more detail.

To trace the recursion, follow the function at each node: it first descends left until there is no child, prints while returning to its parent, and then processes the right subtree. The example’s values therefore appear in the order 3 8 9 10 14. The tree size is five nodes and its edge-based height is two. The program is self-contained; adapt the node value type or add operations while keeping ownership and the chosen height convention clear.