LeetCode 104. Maximum Depth of Binary Tree

Intuition

Use DFS to look at all paths and find the deepest depth

Optimal Solution

go to the deepest child and find depth of left & right by incrementing 1 as you go up layer below is the call order for example

3 /
9 20 /
15 7

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # use dfs to find max depth
        def dfs(node):
            if not node:
                return 0
            left_depth = dfs(node.left)
            right_depth = dfs(node.right)

            return max(left_depth+1, right_depth+1)

        return dfs(root)

Entering Node 3
    Entering Node 9
        Hit None (Base Case) -> Returning 0
        Hit None (Base Case) -> Returning 0
    Leaving Node 9 -> Left: 0, Right: 0
    Entering Node 20
        Entering Node 15
            Hit None (Base Case) -> Returning 0
            Hit None (Base Case) -> Returning 0
        Leaving Node 15 -> Left: 0, Right: 0
        Entering Node 7
            Hit None (Base Case) -> Returning 0
            Hit None (Base Case) -> Returning 0
        Leaving Node 7 -> Left: 0, Right: 0
    Leaving Node 20 -> Left: 1, Right: 1
Leaving Node 3 -> Left: 1, Right: 2

Time Complexity

Time Complexity O(N)

Space Complexity O(H)