https://leetcode.com/problems/maximum-depth-of-binary-tree/description/?envType=study-plan-v2&envId=top-interview-150

C++

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

        vector<pair<int, TreeNode*>> stack;
        stack.push_back(pair<int, TreeNode*>(1, root));
        int max_depth = 0;

        while(!stack.empty()){
            pair<int, TreeNode*> curr = stack.back();
            int curr_depth = curr.first;
            TreeNode* curr_node = curr.second;
            max_depth = max(max_depth, curr_depth);
            stack.pop_back();T
            if (curr_node->left != NULL){
                stack.push_back(pair<int, TreeNode*>(curr_depth+1, curr_node->left));
            }
            if (curr_node->right != NULL){
                stack.push_back(pair<int, TreeNode*>(curr_depth+1, curr_node->right));
            }
        }
        return max_depth;
    }
};

Time Complexity

• Time complexity: $O(N)$
  • You visit every node exactly once in the while loop, doing O(1) work per node (back, pop, two comparisons), so $O(N)$ total.
• Space complexity: $O(N)$
  • Your stack vector holds nodes waiting to be processed. The maximum number of nodes in it at any time depends on tree shape:
    • Worst case (unbalanced): At any point you have at most $O(N)$ nodes queued — for example a completely unbalanced tree where every node branches right still pushes one node at a time, but a wide bushy tree can have many nodes sitting in the stack simultaneously. The true worst case is a perfect binary tree, where the bottom level alone has $N/2$ nodes, so the stack reaches $O(N)$.
    • Best case (linear chain): Only ever $1$ node in the stack at a time → $O(1)$.
  • So overall space is $O(N)$ in the worst case.