Maximum Depth of Binary Tree

Problem statement

Given the root of a binary tree, return its maximum depth — the number of nodes along the longest root-to-leaf path.

Example:

Input:

root = [3, 9, 20, null, null, 15, 7]

Expected output:

3

Why: the longest path is 3 → 20 → 15 (or 3 → 20 → 7), three nodes deep.

Practice on LeetCode: Maximum Depth of Binary Tree

Golang Solution

Recurse on left and right. A null node has depth 0; otherwise the answer is 1 plus the larger child depth.

Time: O(n) — each node visited once
Space: O(h) — recursion stack (h = tree height)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    left := maxDepth(root.Left)
    right := maxDepth(root.Right)

    return 1 + max(left, right)
}