FastPrep
Problem

Key Teams in Tree

Learn this problem
Salesforce logoSalesforceFULLTIMEOA
See Salesforce hiring insights

Problem statement

You are given a tree with n nodes labeled from 0 to n - 1. The tree represents an organizational hierarchy.

A node is a key team if it is an endpoint of at least one longest path in the tree. A longest path in a tree is also called a tree diameter.

Return a binary array answer of length n, where answer[i] = 1 if node i is a key team, and 0 otherwise.

Function

keyTeamsInTree(n: int, edges: int[][]) → int[]

Examples

Example 1

n = 4edges = [[0, 1], [1, 2], [2, 3]]return = [1, 0, 0, 1]

The only diameter is the path from node 0 to node 3, so those two nodes are marked.

Example 2

n = 4edges = [[0, 1], [0, 2], [0, 3]]return = [0, 1, 1, 1]

Every longest path goes between two leaves, so nodes 1, 2, and 3 are all endpoints of some diameter.

Constraints

  • 1 <= n
  • edges.length == n - 1
  • The edges form a tree.

More Salesforce problems

drafts saved locally
public int[] keyTeamsInTree(int n, int[][] edges) {
  // write your code here
}
n4
edges[[0, 1], [1, 2], [2, 3]]
expected[1, 0, 0, 1]
checking account