Binary trees serve as foundational structures for many advanced topics such as dynamic programming and backtracking. Mastery of their traversal methods is essential.

Core Traversal Strategies

Two primary strategies exist: depth-first and breadth-first.

Depth-First Traversal

Explores as far as possible along each branch before backtracking. Variants:

• Pre-order: process current node, then left subtree, then right subtree (current → left → right)
• In-order: process left subtree, then current node, then right subtree (left → current → right)
• Post-order: process left subtree, then right subtree, then current node (left → right → current)

Recursive implementation relies on call stack semantics; iterative versions typically use an explicit stack data structure.

Breadth-First Traversal

Visits nodes level by level using a queue (FIFO behavior). Commonly referred to as level-order traversal.

Node Definition

A binary tree node can be represented as:

struct Node {
    int value;
    Node* leftChild;
    Node* rightChild;
    Node(int v) : value(v), leftChild(nullptr), rightChild(nullptr) {}
};

Storage options include linked representation (pointer-based) or array representation (less common).

Recursive Pre-order Example

Define recursion with three elements: parameters, termination condition, and per-step logic.

class Solver {
public:
    void visit(Node* n, std::vector<int>& out) {
        if (!n) return;
        out.push_back(n->value);      // current
        visit(n->leftChild, out);     // left
        visit(n->rightChild, out);    // right
    }
    std::vector<int> preOrder(Node* root) {
        std::vector<int> res;
        visit(root, res);
        return res;
    }
};

Termination occurs when a null pointer is encountered. Each call appends the current node's value before recursing into children.

Iterative Level-order Traversal

Level-order traversal requires a queue to maintain FIFO access:

class Solver {
public:
    std::vector<std::vector<int>> levelOrder(Node* root) {
        std::queue<Node*> q;
        if (root) q.push(root);
        std::vector<std::vector<int>> levels;
        while (!q.empty()) {
            int layerSize = q.size();
            std::vector<int> layerVals;
            for (int i = 0; i < layerSize; ++i) {
                Node* curr = q.front(); q.pop();
                layerVals.push_back(curr->value);
                if (curr->leftChild) q.push(curr->leftChild);
                if (curr->rightChild) q.push(curr->rightChild);
            }
            levels.push_back(layerVals);
        }
        return levels;
    }
};

Capturing layerSize ensures nodes are grouped per depth level.

Variations on Level-order

• Bottom-up levels: collect levels normally then reverse the container.
• Right-side view: during level iteration, capture the last node of each layer.
• Average per level: accumulate sum for the layer, compute mean after processing all nodes in that layer.
• N-ary tree level-order: enqueue all children of a node instead of just two.
• Maximum per level: track and store the largest value encountered in each layer.

Depth from Level-order

Count iterations of the outer loop to determine tree height:

int treeHeight(Node* root) {
    if (!root) return 0;
    std::queue<Node*> q;
    q.push(root);
    int h = 0;
    while (!q.empty()) {
        int cnt = q.size();
        ++h;
        for (int i = 0; i < cnt; ++i) {
            Node* nd = q.front(); q.pop();
            if (nd->leftChild) q.push(nd->leftChild);
            if (nd->rightChild) q.push(nd->rightChild);
        }
    }
    return h;
}

For minimum depth, stop when a node with no children is found during traversal.

Invert Binary Tree

Swap left and right children at every node.

Recursive approach:

Node* invertRec(Node* root) {
    if (!root) return nullptr;
    std::swap(root->leftChild, root->rightChild);
    invertRec(root->leftChild);
    invertRec(root->rightChild);
    return root;
}

Iterative BFS version:

Node* invertBfs(Node* root) {
    if (!root) return nullptr;
    std::queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        std::swap(cur->leftChild, cur->rightChild);
        if (cur->leftChild) q.push(cur->leftChild);
        if (cur->rightChild) q.push(cur->rightChild);
    }
    return root;
}

Count Nodes in Complete Binary Tree

Perform level-order traversal and increment a counter for each visited node.

int nodeCount(Node* root) {
    if (!root) return 0;
    std::queue<Node*> q;
    q.push(root);
    int total = 0;
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        ++total;
        if (cur->leftChild) q.push(cur->leftChild);
        if (cur->rightChild) q.push(cur->rightChild);
    }
    return total;
}

Symmetry checks and balance verification typically rely on recursive comparison of mirrored positions rather than direct child-node comparison.