mycsmajor
Data structures problem 9 of 30

Depth of a binary tree

  • Data structures
  • Easy

Given the root of a binary tree, return its maximum depth: the number of nodes on the longest path from the root down to a leaf. An empty tree has depth 0.

class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
Show hint

The depth of a tree is 1 plus the depth of its deeper subtree.

Show solution 
def max_depth(root):
    if root is None:
        return 0
    return 1 + max(max_depth(root.left),
                   max_depth(root.right))

The empty tree is the base case. Every other node adds one level on top of its deeper child. Each node is visited once: O(n) time, and O(h) stack space for a tree of height h.

Want a problem like this every day? See today's problem and keep a streak going.