Maximum Depth

LeetCode 104 · View on LeetCode

Recursive DFS to find the maximum depth of a binary tree. Base case: nil returns 0. Recursive case: 1 + max of left and right depths. O(n) time, O(h) space where h is the height.

package main

import "fmt"

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)
	if left > right {
		return left + 1
	}
	return right + 1
}

func main() {
	root := &TreeNode{Val: 3,
		Left: &TreeNode{Val: 9},
		Right: &TreeNode{Val: 20,
			Left:  &TreeNode{Val: 15},
			Right: &TreeNode{Val: 7},
		},
	}
	fmt.Println(maxDepth(root)) // 3

	skewed := &TreeNode{Val: 1,
		Left: &TreeNode{Val: 2,
			Left: &TreeNode{Val: 3},
		},
	}
	fmt.Println(maxDepth(skewed)) // 3
	fmt.Println(maxDepth(nil))    // 0
}