104. Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree

Summary

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.

Approach

DFS.

We pass the current depth through the recursion. Each time we go one level deeper, we add 1 to the depth.

Finally, we compare the left and right depths and return the larger value.

Function

Function dfs(root, depth=0): If root is None: return depth return max(dfs(root.right, depth + 1), dfs(root.left, depth + 1))

Main: return dfs(root)

Complexity

Time Complexity: O(N) Space Complexity: O(N)