Approach

1. For an empty children array, return zero. Otherwise start from root index 0.
2. Define the depth of a missing child (-1) as zero. For each actual node, compute one plus the maximum depth of its left and right children.
3. Use recursion or an explicit stack; the valid-tree contract supplies reachability and unique parents, so no graph repair or cycle detection is required.

Why it works

Every root-to-leaf path through a node continues through one of its children. Taking the larger child depth selects the longest continuation, and adding one counts the current node. Applying this relation from the leaves back to root counts nodes rather than edges.

Complexity

O(n) time because each node is visited once. Recursive depth-first traversal uses O(h) auxiliary stack space for tree height h, O(n) in a chain; returned output is one integer.

Edge cases to check

• An empty tree has depth zero, a single node depth one, and a chain of n nodes depth n.
• A -1 child is missing; do not index the array with it.
• A tree may be unbalanced or have only right children. Leave every child pair unchanged.