Diameter of a Binary Tree

Diameter of a Binary Tree

Find the length of the longest path between any two nodes in a binary tree.

Input format

The first line contains level-order tokens, where N denotes a null node.

Output format

Print the number of edges on the longest node-to-node path.

Constraints

• Values fit in a 64-bit signed integer
• Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

8 42 55 69 18 29 21 33 14 N N 34 15 N N 41 72 N N 82 N 74 N N N N 73 28 N N 35 N N N N 26 64 N N N 95

12

1 39 83 87 21 93 91 47 3 8 N 82 34 N N 44 31 N N N N 61 N N N N N 13 97 52 N N N N 60 N N N 18 54 42

13