Challenge: Leaves and Totals

Lab Python Intermediate 20 points

Print three facts about the tree: the number of nodes, the number of leaves, and the largest value.

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

Nodes: <n>
Leaves: <n>
Max: <value>

Example

Input

8 3 10 1 6 N 14 N N 4

Output

Nodes: 7
Leaves: 3
Max: 14

Sample input available Sample output available

Editor

Python

Hints

A leaf has no left and no right child.

For the max, an empty tree can return float("-inf").

Solution explanation

Three small recursive functions, each visiting every node once.

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 count(n):
    return 0 if n is None else 1 + count(n.left) + count(n.right)


def leaves(n):
    if n is None:
        return 0
    if n.left is None and n.right is None:
        return 1
    return leaves(n.left) + leaves(n.right)


def biggest(n):
    if n is None:
        return float("-inf")
    return max(n.value, biggest(n.left), biggest(n.right))


print("Nodes:", count(root))
print("Leaves:", leaves(root))
print("Max:", biggest(root))

Output

Answer