Compute tree depth and meeting rooms

Solve both coding problems.

Problem 1: Maximum depth of a binary tree

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes on the longest path from the root node down to a leaf node.

Assumptions:

• If the tree is empty, return 0.
• The tree may be highly unbalanced.
• The number of nodes can be up to 100,000, so consider recursion-depth limitations depending on the language.

Example: Input tree: 3, 9, 20, null, null, 15, 7 Output: 3

Problem 2: Minimum meeting rooms

Given an array of meeting time intervals intervals, where each interval is [start, end), return the minimum number of conference rooms required so that all meetings can be held.

Assumptions:

• start < end for every meeting.
• Times are integers.
• Intervals are half-open, so a meeting ending at time 10 does not conflict with another meeting starting at time 10.
• The number of intervals can be up to 100,000.

Example:

Input: [[0, 30], [5, 10], [15, 20]]
Output: 2

Example:

Input: [[7, 10], [10, 12]]
Output: 1

Maximum Depth of a Binary Tree

Given the root of a binary tree, return its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

The tree is provided as a level-order (breadth-first) array values, LeetCode-style: index 0 is the root, and null/None marks a missing child. For example, [3, 9, 20, null, null, 15, 7] encodes a tree with root 3, left child 9, right child 20, and 20's children 15 and 7.

Notes:

• If the tree is empty (values is empty or its first element is null), return 0.
• The tree may be highly unbalanced (a long single chain).
• The number of nodes can be up to 100,000, so prefer an iterative solution to avoid hitting the language's recursion-depth limit.

Constraints

• 0 <= number of nodes <= 100,000
• Node values fit in a 32-bit integer
• The tree may be a long single chain (highly unbalanced)
• An empty tree returns 0

Examples

Example 1

Input: ([3, 9, 20, None, None, 15, 7],)
Output: 3

Explanation: Root 3 -> right child 20 -> leaf 15 (or 7): the longest path has 3 nodes.

Example 2

Input: ([],)
Output: 0

Explanation: Empty tree has depth 0.

Hints

1. Maximum depth equals the number of levels in a breadth-first traversal of the tree.
2. A recursive depth-first solution is concise, but with up to 100,000 nodes a degenerate chain can overflow the call stack — prefer an iterative BFS or an explicit stack.
3. When the input is a level-order array, you can reconstruct parent-to-child links in one left-to-right pass using a queue of parents, consuming two array slots (left, right) per parent and skipping nulls.

Minimum Number of Meeting Rooms

Given an array of meeting time intervals intervals, where each intervals[i] = [start, end) is half-open, return the minimum number of conference rooms required so that all meetings can be held.

Because intervals are half-open, a meeting ending at time 10 does not conflict with another meeting starting at time 10 — they can share a room.

Notes:

• start < end for every meeting.
• All times are integers.
• The number of intervals can be up to 100,000.
• If there are no meetings, return 0.

Constraints

• 0 <= number of intervals <= 100,000
• intervals[i] = [start, end) with start < end
• All times are integers
• Intervals are half-open: a meeting ending at t does not conflict with one starting at t

Examples

Example 1

Input: ([[0, 30], [5, 10], [15, 20]],)
Output: 2

Explanation: [0,30) overlaps both [5,10) and [15,20), so 2 rooms are needed; [5,10) and [15,20) don't overlap each other.

Example 2

Input: ([[7, 10], [10, 12]],)
Output: 1

Explanation: Half-open: the meeting ending at 10 does not conflict with the one starting at 10, so one room suffices.

Hints

1. Decouple starts from ends: sort all start times and all end times into two separate sorted arrays.
2. Sweep with two pointers. The maximum number of meetings that are simultaneously in progress is the answer.
3. Because intervals are half-open, treat a start at time t as NON-conflicting with an end at time t — use a strict start < end comparison so the ending meeting frees its room first.