Maximum Depth of Binary Tree

Problem

Given the root of a binary tree, return its maximum depth.

A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Solution Approach

Expected Time complexity: $O(n)$

Click - to see solution code

C++

class Solution {
    int h;

   public:
    void traverse(TreeNode* root, int hgt) {
        if (!root) return;
        h = max(h, hgt);
        traverse(root->left, hgt + 1);
        traverse(root->right, hgt + 1);
    }

    int maxDepth(TreeNode* root) {
        h = 0;
        traverse(root, 1);
        return h;
    }
};