package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func minDepthIter(root *TreeNode, depth int) int {
	if root.Left == nil && root.Right == nil {
		return depth
	}
	if root.Left == nil {
		return minDepthIter(root.Right, depth+1)
	}
	if root.Right == nil {
		return minDepthIter(root.Left, depth+1)
	}
	return minInt(minDepthIter(root.Left, depth+1), minDepthIter(root.Right, depth+1))
}

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

func main() {
	/**
	 * t1:  5
	 *       \
	 *        4
	 *       / \
	 *      2   3
	 */
	t1rl := TreeNode{2, nil, nil}
	t1rr := TreeNode{3, nil, nil}
	t1r := TreeNode{4, &t1rl, &t1rr}
	t1 := &TreeNode{5, nil, &t1r}
	fmt.Println(minDepth(t1))
	fmt.Println(minDepth(nil))
}