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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Depth of Binary Tree

Number: 104

Difficulty: Easy

Paid? No

Companies: Amazon, LinkedIn, Google, Microsoft, Meta, Arista Networks, Yahoo, Infosys, Apple, Adobe, Yandex, Bloomberg, Uber, SAP

Problem Description

Given the root of a binary tree, determine its maximum depth. The maximum depth is defined as the number of nodes along the longest path from the root node down to the farthest leaf node.

Key Insights

  • Use a recursive strategy (DFS) to traverse the binary tree.
  • At each node, compute the maximum depth of its left and right subtree.
  • The maximum depth at the current node is 1 (current node) plus the maximum of the left and right subtree depths.
  • Alternatively, an iterative approach using BFS (level-order traversal) can be used.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes, since every node is visited once. Space Complexity: O(h) for recursion stack in DFS, where h is the height of the tree (worst-case O(n) for a skewed tree); O(n) for BFS in the worst-case scenario if the tree is balanced.

Solution

The problem is approached using Depth-First Search (DFS) with recursion. The idea is to visit every node and calculate the maximum depth of the left and right subtrees, then add 1 for the current node. This method naturally handles the base case when a null node (empty tree) is reached by returning 0. Alternatively, a Breadth-First Search (BFS) approach can determine the tree level by level, with the total number of levels equaling the maximum depth. Key data structures include recursion call stack for DFS or a queue for BFS.

Code Solutions

# Python implementation using DFS

# 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:
        # Base case: if the node is null, return 0.
        if not root:
            return 0
        
        # Recursively compute the maximum depth of the left subtree.
        left_depth = self.maxDepth(root.left)
        # Recursively compute the maximum depth of the right subtree.
        right_depth = self.maxDepth(root.right)
        
        # Return the greater depth plus one for the current node.
        return 1 + max(left_depth, right_depth)
← Back to All Questions