Loading...
Loading...
Loading...
Meera is drawing her family tree for a school project. Her great-grandfather is at the top, and each person has at most two children drawn below them.
The height of the tree is the number of people on the longest line from the top person straight down to someone with no children. Print the height. An empty drawing has height 0.
N for no node. Children are listed only for real nodes, and N tokens at the end of the line may be left out. For example, 1 2 3 N 4 is root 1 with children 2 and 3, and 4 is the right child of 2. An empty tree is the single token N.Example 1
Input
1 2 3 N 4
Output
3
The longest line is 1 → 2 → 4, with 3 people.
Example 2
Input
7
Output
1
One person alone is one generation.
Try the problem first. Open one hint at a time.
An empty tree has height 0, and a single person has height 1.
The height of a tree is 1 more than the larger of the heights of its left and right parts.
A method that calls itself on both children and returns 0 for a missing child gives the answer in one pass.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor