How deep does the tree go

Easy

2000 ms limit256 MB memoryTrees

Stuck?

Show a hint

The depth of a missing node is 0. The depth of any other is one plus the larger of its two children.

The ideas behind this problem

Recursion: trusting the smaller problem Traversals: four orders, and which question each answers Trees: one thing above, several below

Next in this lesson

Are these two trees identical

Return the maximum depth of a binary tree, which is the number of nodes along the longest path from the root down to a leaf.

How the input is written#

A tree is given level by level, with null where a child is missing. So 3 9 20 null null 15 7 is:

Reading it: 3 is the root. Its children are 9 and 20. Then 9's two children are both null, and 20's are 15 and 7.

Worked example#

For that tree, the depth of any node is one more than the deeper of its two children:

node	left depth	right depth	its depth
9	0	0	1
15	0	0	1
7	0	0	1
20	1	1	2
3	1 (from 9)	2 (from 20)	3

The answer is 3.

Why this is the natural shape for a tree#

The answer for a node depends only on the answers for its children, and those are just smaller versions of the same question. So the whole thing is one line: the depth of a missing node is 0, and the depth of any other is one plus the larger of its children.

An empty tree has depth 0, and that base case is what stops the recursion.

The cost#

Time O(n), since every node is visited once. Memory O(h) where h is the height, because that is how deep the call stack gets. A balanced tree makes that about log n, and a tree that has degenerated into a chain makes it n.

Constraints#

0 <= number of nodes <= 10000
-100 <= value <= 100

Input

root is a count then that many level order tokens, where null marks a missing child.

Output

The maximum depth.

Examples

Input

7
3 9 20 null null 15 7

Output

The longest path is 3, 20, 15, which is three nodes.

Input

3
1 null 2

Output

A root with only a right child is two deep.

Input

Output

An empty tree has depth 0.

Something wrong with this problem? Report an issue

Ready to try it

Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.

Create a free account Sign in

Free, and it stays free. No card.