Find the Maximum Depth of a Binary Tree

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

children = [[1, 2], [-1, -1], [3, -1], [-1, -1]]
Output: 3

The longest root-to-leaf path visits nodes 0, 2, and 3.

children = []
Output: 0