0104. Maximum Depth

Easy | Tree + Level-order Traversal | 24 ms (95.24%), 15.9 MB (92.41%)

❓ Problem Statement

Source: LeetCode - Maximum Depth of Binary Tree GitHub: Solution / Performance

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.

✍🏻 Constraints & Example

💡 Ideas

Extension question of Level-order traversal.

While traversing the tree in level order, we need to record the current level (depth).

🤖 Python3

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        # (base case)
        if not root: return 0
        if not root.left and not root.right: return 1
    
        # ==================================================
        #  Binary Tree                       (Iterative)   =
        # ==================================================
        # time  : O(n)
        # space : O(n), O(log(n)) for average case

        maxDepth = 0
        stack = [root]
        
        while stack:
            # loop through stack for current length, pop the first node
            for i in range(len(stack)):
                node = stack.pop( 0 )
                
                if node.left: stack.append(node.left)
                if node.right: stack.append(node.right)
                    
            maxDepth += 1
            
        return maxDepth
        
        '''
        # ==================================================
        #  Binary Tree                       (Recursive)   =
        # ==================================================
        # time  : O(n)
        # space : O(n), O(log(n)) for average case
        
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
        '''

🤖 Java