A binary tree is given in level order, with -1 marking a missing child (missing children of missing nodes are not listed). Print the height: the number of nodes on the longest path from the root down to a leaf. An empty tree has height 0.
Constraints
- 0 ≤ number of tokens ≤ 200000
- Node values are non-negative integers
Input and output
- Input
- Line 1: t (number of tokens) Line 2: t tokens in level order
- Output
- One integer: the height.
Examples
Input 1
7
3 9 20 -1 -1 15 7Output
3Height 3.
Input 2
0Output
0Empty tree.
Show hints
- Build the tree with a queue, exactly as it was written.
- Counting levels with BFS avoids deep recursion.
Show the explanation
Rebuild the tree with a queue: the first token is the root; then, for each node taken from the queue, the next two tokens are its left and right children (-1 = none). The height is the number of BFS levels. Recursion (1 + max(height(left), height(right))) is the classic answer, but a degenerate tree with 200000 nodes would overflow the call stack in many languages, which is worth mentioning in an interview.
O(n) time and space.
Original UniCircle question. Last reviewed 21 Oct 2026.