FastPrepMaximum Depth of a Rooted Tree
Problems/Maximum Depth of a Rooted Tree

Maximum Depth of a Rooted Tree

Datadog logoDatadog● MediumFULLTIMEPHONE SCREEN
QuestionFunctionExamplesConstraints

Problem statement

Source note: The report asks for maximum tree depth and discusses traversal space complexity. The parent-array interface, node-count convention, empty input, examples, and bounds are supplied for practice. The core task matches the report at about 85%.

Return the maximum number of nodes on a root-to-leaf path in the tree described by parents.

Nodes are numbered from 0 to parents.length - 1. The root is node 0, with parent -1. For every other node i, parents[i] identifies its parent. Each node may have any number of children, and a parent index may be larger than a child index.

Count nodes, including the root and leaf. A single-node tree has depth 1; an empty tree has depth 0.

Function

maxTreeDepth(parents: int[]) → int

Examples

Example 1

parents = [-1,0,0,1,1]return = 3

The path 0 → 1 → 3 contains three nodes. No root-to-leaf path contains more, so the maximum depth is 3.

Example 2

parents = [-1]return = 1

The root is also a leaf. Its path contains one node, so the depth is 1.

Example 3

parents = []return = 0

An empty tree has depth 0.

Constraints

  • 0 <= parents.length <= 5000
  • -1 <= parents[i] <= 4999
  • For nonempty input, parents[0] == -1; every other parent is a valid node index. The parent links form one tree rooted at node 0, with no cycle.
See Datadog hiring insights
Saved
public int maxTreeDepth(int[] parents) {
    // Write your code here.
}
Checking account…