How tall is the tree?

Problem

The height of a binary tree is the number of nodes on the longest path from the root down to a leaf. An empty tree has height 0. The tree may or may not be a binary search tree.

Input, output and limits

Input: Line 1: the tree in level order, keys separated by spaces, with # for a missing child. The children of a missing node are not listed, and trailing # may be left out. A single # is an empty tree.
Output: The height.
Constraints: 0 ≤ number of nodes ≤ 300
1 ≤ each key ≤ 1000000

Examples

Example 1

Input

8 3 10 1 6 # 14 # # 4 7 13

Output

Example 2

Input

Output

Hints

Try the problem first. Open one hint at a time.

Hint 1

The height of a node is 1 plus the larger height of its two children.

Hint 2

A missing child has height 0.

Write your Python code, run it on the examples and submit it to hidden tests.

Solve in the editor

Add a new order numbereasy
Is the price tree valid?medium
Prices in sorted ordereasy
Kth cheapest itemmedium
Cheapest and dearest priceeasy

All Python problems

Problem

Input, output and limits

Examples

Hints

More Binary Search Trees problems

Problem

Input, output and limits

Examples

Hints

More Binary Search Trees problems