#157EasyTrees· Tree Height

Org Chart Depth

A small company models its reporting structure as a binary tree: every employee has at most two direct reports, and the CEO is the root. HR wants to know how long the longest chain of command is, counting the people on it. The **depth** of the org chart is the number of nodes on the longest path that starts at the root and ends at an employee with no direct reports. An empty chart has depth 0, and a chart containing only the CEO has depth 1. Return the depth of the tree.

Input format

`root`: a binary tree given in level order as an array, with `null` for a missing child (as in the examples).

Output format

An integer: the number of nodes on the longest root-to-leaf path.

Examples

Input: root = [3, 9, 20, null, null, 15, 7]

Output: 3

The longest chain is 3 -> 20 -> 15 (or 7), which has three people on it.

Input: root = [1, null, 2]

Output: 2

The CEO has a single report, so the chain 1 -> 2 has two people.

Input: root = []

Output: 0

An empty chart has no one on any path, so the depth is 0.

Constraints

0 <= number of nodes <= 10^4
-1000 <= node value <= 1000
The tree can be completely lopsided, so a path may contain every node.

#tree
#depth-first-search
#breadth-first-search