We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Depth of Binary Tree

Difficulty: Easy

Problem Description

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.

Key Insights

  • The maximum depth of a binary tree can be determined using either depth-first search (DFS) or breadth-first search (BFS).
  • A leaf node is defined as a node that does not have any children.
  • The maximum depth is the longest path from the root to any leaf node.
  • The problem can be approached recursively by calculating the depth of left and right subtrees and returning the maximum of the two depths.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the tree, as we may visit each node once. Space Complexity: O(h) - where h is the height of the tree, due to the stack space used in recursion (for DFS) or the queue space used in BFS.

Solution

To solve the problem of finding the maximum depth of a binary tree, we can use a recursive approach. The algorithm involves checking if the current node is null. If it is, we return a depth of 0. Otherwise, we recursively calculate the maximum depth of the left and right subtrees, and return the greater of the two depths plus one for the current node.

Code Solutions

def maxDepth(root):
    if not root:
        return 0
    else:
        left_depth = maxDepth(root.left)  # Recursively find the depth of the left subtree
        right_depth = maxDepth(root.right)  # Recursively find the depth of the right subtree
        return max(left_depth, right_depth) + 1  # Return the greater depth plus one for the current node
← Back to All Questions