Challenge: Tree Height

Lab Python Beginner 10 points

Print the height of the tree: the number of nodes on the longest path from the root down to a leaf (an empty tree has height 0).

Input

One line: the tree in level order (row by row, left to right), with N for a missing child. For example 1 2 3 N 4 is 1 with children 2 and 3, and 2 has only a right child 4. The starter code already builds the tree for you.

Output

One number.

Example

Input

1 2 3 N 4

Output

Sample input available Sample output available

Editor

Python

Hints

An empty tree (None) has height 0.

height = 1 + the bigger of the left and right heights.

Solution explanation

Each node is visited once: O(n).

Show solution

from collections import deque


class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


def build(tokens):
    """Build a tree from level-order values; "N" means no node."""
    if not tokens or tokens[0] == "N":
        return None
    root = Node(int(tokens[0]))
    q = deque([root])
    i = 1
    while q and i < len(tokens):
        node = q.popleft()
        if tokens[i] != "N":
            node.left = Node(int(tokens[i]))
            q.append(node.left)
        i += 1
        if i < len(tokens) and tokens[i] != "N":
            node.right = Node(int(tokens[i]))
            q.append(node.right)
        i += 1
    return root


root = build(input().split())


def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


print(height(root))

Output

Answer