Maximum Depth of a Binary Tree

Given a binary tree, determine its maximum depth - the number of nodes along the longest path from the root node to the farthest leaf node.

Recursive Approach

Using postorder traversal (left-right-root) to calculate node height:

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class DepthCalculator {
public:
    int computeMaxDepth(TreeNode* node) {
        if (node == nullptr) return 0;
        int leftHeight = computeMaxDepth(node->left);
        int rightHeight = computeMaxDepth(node->right);
        return 1 + std::max(leftHeight, rightHeight);
    }
};

Iterative Approach

Using level-order traversal with a queue:

class LevelDepth {
public:
    int findMaxDepth(TreeNode* root) {
        if (root == nullptr) return 0;
        
        std::queue<TreeNode*> nodeQueue;
        nodeQueue.push(root);
        int maxLevels = 0;
        
        while (!nodeQueue.empty()) {
            int currentLevelSize = nodeQueue.size();
            maxLevels++;
            
            for (int i = 0; i < currentLevelSize; i++) {
                TreeNode* currentNode = nodeQueue.front();
                nodeQueue.pop();
                
                if (currentNode->left) nodeQueue.push(currentNode->left);
                if (currentNode->right) nodeQueue.push(currentNode->right);
            }
        }
        return maxLevels;
    }
};

Maximum Depth of N-ary Trees

Extending the binary tree approach to handle N-ary trees:

struct NaryNode {
    int val;
    std::vector<NaryNode*> children;
};

class NaryDepth {
public:
    int calculateMaxDepth(NaryNode* root) {
        if (root == nullptr) return 0;
        
        int maxChildDepth = 0;
        for (NaryNode* child : root->children) {
            maxChildDepth = std::max(maxChildDepth, calculateMaxDepth(child));
        }
        return 1 + maxChildDepth;
    }
};

Minimum Depth of Binary Trees

Finding the shortest path from root to any leaf node:

class MinDepthFinder {
public:
    int findMinDepth(TreeNode* node) {
        if (node == nullptr) return 0;
        
        int leftMin = findMinDepth(node->left);
        int rightMin = findMinDepth(node->right);
        
        if (node->left == nullptr && node->right != nullptr) {
            return 1 + rightMin;
        }
        if (node->right == nullptr && node->left != nullptr) {
            return 1 + leftMin;
        }
        
        return 1 + std::min(leftMin, rightMin);
    }
};

Counting Nodes in Complete Binary Trees

Genarel Binary Tree Approach

class NodeCounter {
public:
    int countAllNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        return 1 + countAllNodes(root->left) + countAllNodes(root->right);
    }
};

Optimized Complete Binary Tree Approach

Leveraging compelte binary tree properties for efficiency:

class CompleteTreeCounter {
public:
    int countCompleteNodes(TreeNode* root) {
        if (root == nullptr) return 0;
        
        TreeNode* leftSubtree = root->left;
        TreeNode* rightSubtree = root->right;
        int leftDepth = 0, rightDepth = 0;
        
        while (leftSubtree) {
            leftSubtree = leftSubtree->left;
            leftDepth++;
        }
        while (rightSubtree) {
            rightSubtree = rightSubtree->right;
            rightDepth++;
        }
        
        if (leftDepth == rightDepth) {
            return (1 << (leftDepth + 1)) - 1;
        }
        
        return 1 + countCompleteNodes(root->left) + countCompleteNodes(root->right);
    }
};

Stack Operasions for Tree Traversal

Essential stack operations used in iterative tree traversals:

#include <stack>
#include <string>

// Stack declaration with custom underlying container
std::stack<std::string, std::list<std::string>> stringStack;

// Core stack operations:
// - top(): Returns reference to top element
// - push(): Adds element to top
// - pop(): Removes top element
// - size(): Returns number of elements
// - empty(): Checks if stack is empty
// - emplace(): Constructs element in place at top
// - swap(): Exchanges contents with another stack