Binary tree depth and level order

1package main
2
3import "fmt"
4
5type Tree struct {
6	Val         int
7	Left, Right *Tree
8}
9
10// maxDepth is the classic recursion: a nil tree has depth 0.
11func maxDepth(t *Tree) int {
12	if t == nil {
13		return 0
14	}
15	return 1 + max(maxDepth(t.Left), maxDepth(t.Right))
16}
17
18// levels is breadth-first search with a slice as the queue.
19func levels(root *Tree) [][]int {
20	var out [][]int
21	if root == nil {
22		return out
23	}
24	queue := []*Tree{root}
25	for len(queue) > 0 {
26		n := len(queue) // everything in the queue now is one level
27		var level []int
28		for _, t := range queue[:n] {
29			level = append(level, t.Val)
30			if t.Left != nil {
31				queue = append(queue, t.Left)
32			}
33			if t.Right != nil {
34				queue = append(queue, t.Right)
35			}
36		}
37		queue = queue[n:] // drop the level we just finished
38		out = append(out, level)
39	}
40	return out
41}
42
43func main() {
44	//       3
45	//      / \
46	//     9  20
47	//        / \
48	//      15   7
49	root := &Tree{3, &Tree{Val: 9}, &Tree{20, &Tree{Val: 15}, &Tree{Val: 7}}}
50	fmt.Println(maxDepth(root))             // 3
51	fmt.Println(levels(root))               // [[3] [9 20] [15 7]]
52	fmt.Println(maxDepth(nil), levels(nil)) // 0 []
53}