Skip to main content

#104. Maximum Depth of Binary Tree | LeetCode Python Solution

Problem​

LeetCode Problem

  1. Maximum Depth of Binary Tree

Python Solution​

# 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:
        # Return 0 when the tree is empty
        if root is None:
            return 0

        # Return 1 when the root node is the only tree node
        if root.left is None and root.right is None:
            return 1

        # If we are here, the tree height is at least 1
        tree_height = 1

        # Push the root node to the stack along with its current level 1
        node_stack = [[root, 1]]
        while node_stack:
            # Pop from the stack
            curr = node_stack.pop()

            # If we just popped a leaf node, find out its level and update tree_height variable if needed
            if (curr[0].left is None and curr[0].right is None):
                tree_height = max(tree_height, curr[1])

            # Push left child along with its level to the stack
            if curr[0].left is not None:
                node_stack.append([curr[0].left, curr[1] + 1])

             # Push right child along with its level to the stack
            if curr[0].right is not None:
                node_stack.append([curr[0].right, curr[1] + 1])

        return tree_height