104. Maximum Depth of Binary Tree

104. Maximum Depth of Binary Tree
Photo by Jeferson Argueta / Unsplash

Submission

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.

Example 1:

Input: root = [3,9,20,null,null,15,7] Output: 3

Example 2:

Input: root = [1,null,2] Output: 2

Solution

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        # It's easier to use our own function so we can avoid self.
        # cleaner too
        def calculate(root):
            # Basecase always first in recursive algos
            if root == None:
                return 0
            
            # calculate left then right, order doesn't matter but this is a DFS search which is something we can say in an interview to sound smarter
            left = calculate(root.left)
            right = calculate(root.right)

            # add + 1 to the depth as we've gone down a level
            # we only care about the max, so calculate the max of both subtrees
            return 1 + max(left, right)
        return calculate(root)