Maximum Depth of Binary Tree

Sources: leetcode 104

Rating: easy

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

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def maxDepth(root: TreeNode) -> int:
    # return the maximum depth of the tree

Solution

Iterate through the tree using a queue, starting with the root node and its level. Use a variable mdepth to store the largest depth value seen.

def maxDepth(root):
    if root is None:
        return []
    queue = [(root, 0)]
    mdepth = 0
    while queue:
        node, level = queue.pop(0)
        # iterate through tree
    return mdepth

Each time a level is checked, compare it against mdepth and update as necessary

def maxDepth(root):
    if root is None:
        return []
    queue = [(root, 0)]
    mdepth = 0
    while queue:
        node, level = queue.pop(0)
        mdepth = max(mdepth, level)
        # iterate through tree
    return mdepth

Finally, add the child nodes to the queue and continue the iteration through the tree.

Final Code

def maxDepth(root):
    if root is None:
        return []
    queue = [(root, 0)]
    mdepth = 0
    while queue:
        node, level = queue.pop(0)
        mdepth = max(mdepth, level)
        if node.left:
            queue.append([node.left, level+1])
        if node.right:
            queue.append([node.right, level+1])
    return mdepth

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s