Algorithm Puzzles: Maximum Depth of Binary Tree

Posted on In Views: Word count in article: 119 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Maximum Depth of Binary Tree

Puzzle

Puzzle from leetcode:

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

It’ an easy puzzle can be resolved via DFS:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxDepth(const TreeNode* root) const {
        if(root == nullptr) {
            return 0;
        }

        return dfs(root, 1);
    }
private:
    int dfs(const TreeNode* root, const int depth) const {
        int ret;

        if(root == nullptr) {
            return depth - 1;
        }

        ret = std::max(dfs(root->left, depth + 1), dfs(root->right, depth + 1));
 
        return ret;
    }
};

T.C.: O(n)
S.C.: O(n)