C++ Binary Trees

A binary tree is a data structure made of nodes, where each node holds a value and points to at most two children: a left child and a right child. Binary trees are the foundation for many other structures — binary search trees, heaps, expression trees, and balanced trees like AVL and red-black trees. Understanding how they are built and traversed with raw pointers is one of the most important skills in C++ data structures, because it teaches you exactly how recursion, the heap, and pointers work together.

Overview: What Is a Binary Tree?

Unlike an array or a std::vector, a binary tree does not store its elements contiguously in memory. Instead, each element lives in its own heap-allocated node, and nodes are linked together with pointers. This gives trees a very different performance profile: insertion and lookup can be much faster than a linear scan (when the tree is balanced), but there is pointer-chasing overhead and no cache-friendly contiguous layout.

Some vocabulary you will see throughout this lesson:

• Root — the single topmost node of the tree (it has no parent).
• Leaf — a node with no children (both left and right are nullptr).
• Subtree — the tree formed by a node and all of its descendants.
• Depth of a node — the number of edges from the root down to that node.
• Height of the tree — the number of edges on the longest path from the root down to a leaf.
• Binary Search Tree (BST) — a binary tree with the ordering rule: everything in a node’s left subtree is smaller, everything in its right subtree is larger.

Internally, each node is a small heap-allocated block containing the stored value plus two pointers (8 bytes each on a 64-bit system). Building a tree means calling new repeatedly and wiring those pointers together; traversing or searching a tree means following those pointers with recursive function calls, each of which pushes a new stack frame. A tree with height h requires at most h nested recursive calls, which is why keeping trees balanced matters — an unbalanced tree can degrade toward a linked list with height close to the number of elements.

Syntax

A binary tree node is almost always written as a small struct holding a value and two self-referencing pointers:

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

Node* root = nullptr;              // an empty tree
root = new Node(10);               // a tree with one node
root->left = new Node(5);          // attach a left child
root->right = new Node(15);        // attach a right child

Part	Meaning
data	The value stored in this node (any type — int here for simplicity).
left / right	Pointers to child nodes, or nullptr if there is no child.
new Node(value)	Allocates a node on the heap and returns a pointer to it.
nullptr	Represents \”no subtree here\” — every recursive function must check for it as its base case.

Examples

Example 1: Building a Tree Manually and Preorder Traversal

#include <iostream>
using namespace std;

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

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

int main() {
    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 << \"Preorder traversal: \";
    preorder(root);
    cout << endl;

    return 0;
}

Output:
Preorder traversal: 10 5 3 7 15 

This example builds a five-node tree by hand and links the nodes with pointer assignments. preorder visits a node before its children: it prints the current node’s data, then recurses into left, then into right. The if (node == nullptr) return; line is the recursion’s base case — without it, the function would try to dereference a null pointer and crash.

Example 2: A Binary Search Tree with Inorder Traversal

#include <iostream>
using namespace std;

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

Node* insert(Node* node, int value) {
    if (node == nullptr) {
        return new Node(value);
    }
    if (value < node->data) {
        node->left = insert(node->left, value);
    } else if (value > node->data) {
        node->right = insert(node->right, value);
    }
    return node;
}

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

int main() {
    Node* root = nullptr;
    int values[] = {50, 30, 70, 20, 40, 60, 80};

    for (int v : values) {
        root = insert(root, v);
    }

    cout << \"Inorder traversal (sorted): \";
    inorder(root);
    cout << endl;

    return 0;
}

Output:
Inorder traversal (sorted): 20 30 40 50 60 70 80 

This is a real binary search tree: insert compares the new value against the current node and recurses left or right, always returning the (possibly new) subtree so the caller can rewire its own pointer — that node->left = insert(node->left, value); pattern is the standard, safe way to insert into a tree without needing pointer-to-pointer tricks. Because a BST keeps everything smaller to the left and larger to the right, an inorder traversal (left, node, right) always visits the values in sorted order — this is one of the most useful properties of BSTs.

Example 3: A Reusable BST Class with Search and Height

#include <iostream>
#include <algorithm>
using namespace std;

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

class BST {
private:
    Node* root;

    Node* insertNode(Node* node, int value) {
        if (node == nullptr) return new Node(value);
        if (value < node->data) node->left = insertNode(node->left, value);
        else if (value > node->data) node->right = insertNode(node->right, value);
        return node;
    }

    bool searchNode(Node* node, int value) const {
        if (node == nullptr) return false;
        if (node->data == value) return true;
        if (value < node->data) return searchNode(node->left, value);
        return searchNode(node->right, value);
    }

    int heightOf(Node* node) const {
        if (node == nullptr) return -1;
        int leftHeight = heightOf(node->left);
        int rightHeight = heightOf(node->right);
        return 1 + max(leftHeight, rightHeight);
    }

    void destroy(Node* node) {
        if (node == nullptr) return;
        destroy(node->left);
        destroy(node->right);
        delete node;
    }

public:
    BST() : root(nullptr) {}
    ~BST() { destroy(root); }

    void insert(int value) { root = insertNode(root, value); }
    bool contains(int value) const { return searchNode(root, value); }
    int height() const { return heightOf(root); }
};

int main() {
    BST tree;
    int values[] = {8, 3, 10, 1, 6, 14, 4, 7, 13};
    for (int v : values) {
        tree.insert(v);
    }

    cout << \"Contains 6? \" << (tree.contains(6) ? \"yes\" : \"no\") << endl;
    cout << \"Contains 99? \" << (tree.contains(99) ? \"yes\" : \"no\") << endl;
    cout << \"Tree height: \" << tree.height() << endl;

    return 0;
}

Output:
Contains 6? yes
Contains 99? no
Tree height: 3

This example wraps the raw pointers inside a class so callers never touch Node* directly. The destructor calls destroy, which recursively deletes every node (postorder: children first, then the node itself) so the tree cleans up after itself with no memory leak — a pattern you should use any time you own heap-allocated nodes.

How Traversal and Insertion Work Under the Hood

Every recursive tree function follows the same shape: check for nullptr (the base case, an empty subtree), then do work on the current node and recurse into its children. Each recursive call opens a new stack frame holding that call’s local variables and its return address. The order in which you do \”visit the node\” relative to the two recursive calls determines the traversal type:

Traversal	Order	Typical use
Preorder	node, left, right	Copying/serializing a tree’s shape
Inorder	left, node, right	Reading a BST’s values in sorted order
Postorder	left, right, node	Deleting a tree (children freed before parent)
Level-order	breadth-first, using a queue	Printing a tree row by row

Insertion into a BST walks down from the root, comparing the new value at each node and choosing left or right, until it reaches a nullptr slot — that is where the new node is attached. The trick used in the examples above, node->left = insert(node->left, value);, works because each recursive call returns the (possibly newly-created) subtree root back up the call chain, letting every ancestor re-link its own pointer. This avoids needing a Node*& reference parameter while still correctly updating the tree, including the very first insertion into an empty tree.

Common Mistakes

Mistake 1: Passing the root by value and expecting it to update

#include <iostream>
using namespace std;

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

void insertWrong(Node* node, int value) {
    if (node == nullptr) {
        node = new Node(value);   // only rebinds the local copy of the pointer
        return;
    }
    if (value < node->data) insertWrong(node->left, value);
    else insertWrong(node->right, value);
}

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

int main() {
    Node* root = nullptr;
    insertWrong(root, 50);
    insertWrong(root, 30);
    insertWrong(root, 70);

    cout << \"Tree contents: \";
    inorder(root);
    cout << \"(nothing printed - root is still null)\" << endl;

    return 0;
}

Output:
Tree contents: (nothing printed - root is still null)

Pointers are passed by value in C++, so reassigning the parameter node inside insertWrong only changes the function’s local copy — it never updates the caller’s root. Every call into an empty tree silently does nothing, and root stays nullptr forever. The fix, shown in Example 2, is to have the function return the (possibly new) node and have every caller reassign: root = insert(root, value);. That way the update always propagates back up, even for the very first insertion.

Mistake 2: Using = instead of == inside a condition

#include <iostream>
using namespace std;

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

bool searchBuggy(Node* node, int target) {
    if (node == nullptr) return false;
    if (node->data = target) return true;   // bug: assignment, not comparison
    if (target < node->data) return searchBuggy(node->left, target);
    return searchBuggy(node->right, target);
}

int main() {
    Node root(50);
    root.left = new Node(30);
    root.right = new Node(70);

    cout << \"Searching for 999: \"
         << (searchBuggy(&root, 999) ? \"found\" : \"not found\") << endl;
    cout << \"Root data is now: \" << root.data << endl;

    return 0;
}

Output:
Searching for 999: found
Root data is now: 999

The condition if (node->data = target) compiles because an assignment expression evaluates to the assigned value, and any non-zero value is truthy — but it silently overwrites node->data with target and reports \”found\” even though 999 was never in the tree. The corrected line simply uses ==: if (node->data == target) return true;. Many compilers warn about this (\”suggest parentheses around assignment\”), so always build with warnings enabled and take them seriously.

Best Practices

• Always check for nullptr as the first line of any recursive tree function — it is the base case that stops the recursion.
• Prefer the \”return the new subtree and reassign\” pattern (node->left = insert(node->left, v);) over passing the root by value, which cannot update an empty tree.
• Give every tree a destructor (or use std::unique_ptr<Node> for left/right) so nodes are freed automatically and you avoid memory leaks.
• Delete a subtree with a postorder walk (children before parent) — deleting the parent first would strand its children with no way to reach them.
• Compile with warnings enabled (-Wall -Wextra) so mistakes like = vs == are caught before they ship.
• For very deep or attacker-controlled trees, be aware that recursive traversal can overflow the call stack; an iterative traversal using an explicit std::stack or std::queue avoids that risk.
• A plain BST can degenerate into a linked list (height ~ n) if values are inserted in sorted order — for guaranteed balance, use a self-balancing tree such as std::map/std::set (typically red-black trees) or implement AVL rotations.

Practice Exercises

• Write a recursive function int countNodes(Node* root) that returns the total number of nodes in a binary tree. Test it on the tree from Example 3 (expected result: 9).
• Write a recursive function bool isBST(Node* root) that checks whether a binary tree satisfies the binary-search-tree ordering property (hint: pass down a valid min/max range as you recurse, rather than just comparing to immediate children).
• Add a level-order traversal function void levelOrder(Node* root) that prints the tree row by row using a std::queue<Node*> instead of recursion. Run it on Example 2’s tree and check the output groups values by depth: 50, then 30 70, then 20 40 60 80.

Summary

• A binary tree stores each element in its own heap-allocated node with up to two child pointers, left and right.
• A binary search tree keeps smaller values to the left and larger values to the right, which makes an inorder traversal produce sorted output.
• Preorder, inorder, postorder, and level-order are the four standard traversal orders, each useful for a different task (copying, sorting, deleting, printing by depth).
• Recursive tree functions must always check for nullptr as a base case, and insertion should reassign the returned subtree rather than relying on pass-by-value pointer updates.
• Clean up owned nodes with a postorder delete (or use smart pointers) to avoid memory leaks, and keep an eye on tree balance since an unbalanced BST degrades toward linked-list performance.