A binary tree is given in level order: the root, then the nodes of each level from left to right, with null where a child is missing. (The children of a missing node are not listed.) Find its depth: the number of nodes on the longest path from the root down to a leaf.
Input
One line: the level-order list, values separated by spaces. The first entry is not null. At most 10⁴ entries.
Output
The depth.
Examples
Example 1 · Input
3 9 20 null null 15 7
Expected output
3
Example 2 · Input
1 null 2
Expected output
2
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Build the tree from the level-order list with a queue: each node takes the next two entries as its children.
Hint 2
depth(None) = 0; depth(node) = 1 + max(depth(left), depth(right)).
Hint 3
For very deep trees, a level-by-level BFS avoids Python's recursion limit.
Solution
Show one correct solution (try it yourself first)
from collections import deque
values = input().split()
root = [values[0], None, None] # [value, left, right]
queue = deque([root])
i = 1
while queue and i < len(values):
node = queue.popleft()
for side in (1, 2):
if i < len(values) and values[i] != "null":
node[side] = [values[i], None, None]
queue.append(node[side])
i += 1
depth = 0
level = [root]
while level: # level by level, so very deep trees are fine
depth += 1
level = [child for node in level for child in (node[1], node[2]) if child]
print(depth)