LeetCode #104: Maximum Depth of Binary Tree

LeetCode Solutions

https://leetcode.com/problems/maximum-depth-of-binary-tree/

The problem asks us to find the maximum depth of a binary tree, which is defined as the number of nodes along the longest path from the root node down to the farthest leaf node. We can solve this problem by using a recursive approach to traverse the tree and keep track of the depth.

Here are the steps to solve the problem:

  1. We start by checking if the root node is null. If it is, then the depth of the tree is zero and we return 0.
  2. If the root node is not null, we recursively calculate the maximum depth of the left subtree and the maximum depth of the right subtree.
  3. We then return the maximum of these two depths plus one, since we need to add one for the current node.
  4. The recursion continues until we reach the leaf nodes, at which point we return 0.

Here’s the Python code that implements this algorithm:

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        else:
            left_depth = self.maxDepth(root.left)
            right_depth = self.maxDepth(root.right)
            return max(left_depth, right_depth) + 1

The time complexity of this algorithm is O(n), where n is the number of nodes in the binary tree. This is because we visit each node exactly once. The space complexity is O(h), where h is the height of the binary tree. This is because the maximum amount of memory used by the algorithm at any given time is the height of the call stack due to recursion.

In conclusion, the above algorithm can be used to find the maximum depth of a binary tree in an efficient manner. The recursive approach allows us to traverse the tree and keep track of the depth without using additional data structures.