Loading page…
Practice problem · easy
A team chat app shows the company directory as an org chart. Each person has at most two direct reports, so the chart is a binary tree. The person at the top is the head of the company.
The design team wants to know how many levels the chart has, so that the page can leave enough room. A large company has up to 100,000 people.
Write org_depth(left, right).
0 to n - 1, and person 0 is the head.left[i] and right[i] are the numbers of the people who report directly to person i, or -1 where there is no one.Input: left = [1, 3, -1, -1, -1], right = [2, 4, -1, -1, -1]
Output: 3| Level | People on it | Next level |
|---|---|---|
| 1 | 0 | 1 and 2 |
| 2 | 1, 2 | 3 and 4 (person 2 has no one) |
| 3 | 3, 4 | none: stop |
Three levels have people on them, so the answer is 3.
Input: left = [-1], right = [-1]
Output: 1The head with no reports is one level.
Input: left = [1, 2, 3, -1], right = [-1, -1, -1, -1]
Output: 4Each person has one report, so the chart is a chain of four.
1 ≤ length of left = length of right ≤ 10^5-1 or a person number from 1 to n - 10: nobody has two managers, and there are no loopsA chart that is a chain of 100,000 people is allowed. A solution that calls itself once for each report would need 100,000 nested calls, and Python and Java stop long before that.
Counting levels one at a time with a loop never nests, and it touches each person once.
org_depth · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.