Minimum Depth of Binary Tree

Problem statement

A maintenance robot enters a branching corridor map at its root. It can finish an inspection only at a terminal station, so the planner wants the shortest route from the entrance to any station with no outgoing branches. Your task Find the minimum depth of the binary tree: the smallest number of nodes on a root-to-leaf path. Important details An absent child is not a terminal station. When a node has just one child, a valid route must continue through that child. An empty tree has depth zero, while a single-node tree has depth one. Worked example In a chain of three stations, the first two each have a child. Only the third is a leaf, so the minimum depth is 3 even though each earlier station has an absent branch.

Input format

The first line contains n. The next n lines contain value left right for nodes 0 through n-1. Child indices are -1 when absent. Node 0 is the root when n > 0. The records form one valid binary tree; n = 0 represents an empty tree.

Output format

Print the minimum depth.

Constraints

0 <= n <= 2000; -1000 <= value <= 1000. Child indices are -1 or valid node indices; no cycles or shared children.

Sample input

3
1 1 -1
2 2 -1
3 -1 -1

Sample output

3