Longest Path in a Binary Tree

Given a binary tree, your task is to determine the length of the longest path from the root node to any leaf node. The length is defined as the number of edges in the path. In particular, if the binary tree is empty, the answer should be -1.

We represent the tree in level order traversal where the string null represents a missing node. For example, the binary tree:

      1
     / \
    2   3
   / \
  4   5

is represented as: 1 2 3 4 5

The longest path for the above tree is from 1 to 2 to 4 (or 5), which has 2 edges.

The key idea is to construct the tree from the given input and then use a recursive algorithm to compute the height of the tree (in terms of nodes) and subtract 1 to get the number of edges.

inputFormat

The input is provided via standard input (stdin) as a single line containing the level order traversal of the binary tree. Each node value is separated by a space. Use the string null to denote the absence of a node. For example:

1 2 3 4 5

outputFormat

Output via standard output (stdout) a single integer representing the number of edges in the longest path from the root to a leaf. If the tree is empty, output -1.## sample

1 2 3 4 5

2