Find the Maximum Depth of a Binary Tree
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Find the maximum depth of a binary tree. The depth is the number of nodes on the longest path from the root to a leaf.
### Function Contract
Implement `maximum_tree_depth(children) -> int`.
For a portable interface, `children` is an array of pairs. Node identifiers are `0` through `n - 1`, and `children[i] = [left, right]` gives node `i`'s left and right child identifiers. A missing child is encoded as `-1`. If the tree is nonempty, node `0` is the root.
### Constraints and Clarifications
These encodings and size bounds are explicit practice assumptions.
- `0 <= n <= 200000`.
- The input represents one valid binary tree: all nodes are reachable from the root, there are no cycles, and each nonroot node has exactly one parent.
- Each child identifier is `-1` or a valid node identifier.
- Return `0` for an empty tree and `1` for a tree containing only its root.
- A tree may be highly unbalanced.
- Aim for `O(n)` time.
### Examples
```text
children = [[1, 2], [-1, -1], [3, -1], [-1, -1]]
Output: 3
```
The longest root-to-leaf path visits nodes `0`, `2`, and `3`.
```text
children = []
Output: 0
```
```hint Track depth along a traversal
Each child is one level deeper than its parent. Consider how your traversal behaves when every node has only one child.
```
Overview: Find binary-tree depth from a portable child-index representation, including empty trees and highly unbalanced root-to-leaf paths.
Read the full LinkedIn Software Engineer interview experience this question came from
Find the maximum depth of a binary tree. The depth is the number of nodes on the longest path from the root to a leaf.
Implement `maximum_tree_depth(children)` returning an integer.
The tree is given as an array of pairs `children` of length `n`. Node identifiers are `0` through `n - 1`, and `children[i] = [left, right]` gives node `i`'s left and right child identifiers. A missing child is encoded as `-1`. If the tree is nonempty, node `0` is the root. Node identifiers are not required to follow any particular order (a child may have a smaller identifier than its parent).
Return `0` for an empty tree (`n = 0`) and `1` for a tree containing only its root. The tree may be highly unbalanced (for example, a single chain of `n` nodes). The answer is at most `n`, so it always fits in a 32-bit signed integer.
### Example 1
```text
children = [[1, 2], [-1, -1], [3, -1], [-1, -1]]
Output: 3
```
The longest root-to-leaf path visits nodes `0`, `2`, and `3`.
### Example 2
```text
children = []
Output: 0
```
The tree is empty.
### Constraints
- `0 <= n <= 200000`, where `n = len(children)`.
- The input represents one valid binary tree: all nodes are reachable from the root, there are no cycles, and each nonroot node has exactly one parent.
- Each child identifier is `-1` or a valid node identifier in `[0, n - 1]`.
- Aim for `O(n)` time.
Constraints
- 0 <= n <= 200000, where n = len(children)
- children[i] = [left, right]; each entry is -1 (missing) or a valid node id in [0, n - 1]
- The input is one valid binary tree rooted at node 0 when nonempty: all nodes reachable, no cycles, each nonroot node has exactly one parent
- Return 0 for an empty tree and 1 for a tree containing only its root
- The tree may be highly unbalanced
- Aim for O(n) time
Examples
Input: ([[1, 2], [-1, -1], [3, -1], [-1, -1]],)
Expected Output: 3
Explanation: Source example: the deepest leaf is in the right subtree via 0 -> 2 -> 3 while node 1 is a shallow left leaf.
Input: ([],)
Expected Output: 0
Explanation: Empty tree has depth 0.
Hints
- Each child is one level deeper than its parent.
- Consider how your traversal behaves when every node has only one child and the tree is 200000 levels deep.
- Node ids need not appear in parent-before-child order, so start from node 0 and follow the child links.