Maximum Depth of a Binary Tree

The maximum depth of a binary tree is defined as the number of nodes along the longest path from the root node down to the farthest leaf node. A leaf node is a node that has no children. This problem can be solved using either a recursive depth-first search approach or an iterative breadth-first search approach.

Recursive Solution

The recursive approach leverages post-order traversal (left-right-root). For each node, the maximum depth is calculated as one (for the current node) plus the maximum depth of its left and right subtrees. When we encounter a null node, we return 0.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int value;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : value(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : value(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *l, TreeNode *r) : value(x), left(l), right(r) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int leftSubtreeDepth = maxDepth(root->left);
        int rightSubtreeDepth = maxDepth(root->right);
        
        return 1 + max(leftSubtreeDepth, rightSubtreeDepth);
    }
};

Iterative Soultion

The iterative approach uses level-order traversal (BFS). The number of levels processed equals the maximum depth of the tree. We maintain a queue to process nodes level by level, incrementing a counter after each complete level.

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }

        int currentDepth = 0;
        queue<TreeNode*> nodeQueue;
        nodeQueue.push(root);

        while (!nodeQueue.empty()) {
            int nodesInCurrentLevel = nodeQueue.size();
            currentDepth++;

            for (int i = 0; i < nodesInCurrentLevel; ++i) {
                TreeNode* node = nodeQueue.front();
                nodeQueue.pop();

                if (node->left != nullptr) {
                    nodeQueue.push(node->left);
                }
                if (node->right != nullptr) {
                    nodeQueue.push(node->right);
                }
            }
        }

        return currentDepth;
    }
};

Maximum Depth of an N-ary Tree

The same principle applies to N-ary trees, where each node can have any number of children. The solution approaches remain similar: recursive traversal for computing subtree depths and iterative level-order traversal for counting levels.

Recursive Solution

For the recursive approach, we iterate through all children of each node, compute thier depths recursively, and take the maximum. The depth of the current node is one plus this maximum value.

/*
class Node {
public:
    int value;
    vector<Node*> children;

    Node() : value(0) {}
    Node(int val) : value(val) {}
    Node(int val, vector<Node*> childList) : value(val), children(childList) {}
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == nullptr) {
            return 0;
        }

        int maxChildDepth = 0;
        for (Node* child : root->children) {
            maxChildDepth = max(maxChildDepth, maxDepth(child));
        }

        return 1 + maxChildDepth;
    }
};

Iterative Solution

The iterative approach for N-ary trees follows the same level-order pattern. After processing all nodes at the current level, we increment the depth counter. The key difference is that we enqueue all children of each node rather than just left and right.

/*
class Node {
public:
    int value;
    vector<Node*> children;

    Node() : value(0) {}
    Node(int val) : value(val) {}
    Node(int val, vector<Node*> childList) : value(val), children(childList) {}
};
*/

class Solution {
public:
    int maxDepth(Node* root) {
        if (root == nullptr) {
            return 0;
        }

        int depth = 0;
        queue<Node*> nodeQueue;
        nodeQueue.push(root);

        while (!nodeQueue.empty()) {
            int levelSize = nodeQueue.size();
            depth++;

            for (int i = 0; i < levelSize; ++i) {
                Node* current = nodeQueue.front();
                nodeQueue.pop();

                for (Node* child : current->children) {
                    if (child != nullptr) {
                        nodeQueue.push(child);
                    }
                }
            }
        }

        return depth;
    }
};