Intuition

Use recursion to traverse the tree, always returning the max value of the right and left tree.

Approach

Complexity

  • Time complexity: O(n)

  • Space complexity: O(log(n)), in case the tree is balanced

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        return self.maxD(root, 0)
    
    def maxD(self, root, level):
        if not root:
            return level
        return max(self.maxD(root.left, level+1),self.maxD(root.right, level+1))