FastPrepTree Node With Maximum Beauty
Problems/Tree Node With Maximum Beauty

Tree Node With Maximum Beauty

C3.ai logoC3.ai● HardNEW GRADOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: In a 2022 C3.ai new grad coding assessment, the input was a tree with a weight on each node. A node's beauty adds up its distance to every other node times that node's weight, and the task was to find the node with the highest beauty in a tree of up to 10^5 nodes.

The report does not say whether to return the node or its beauty, how to break ties, or what the weights can be. Here, you return the node's label, the smallest label wins a tie, and weights are 0 to 10^4. The tree has at most 2 * 10^4 nodes instead of 10^5 so the tests run in time.

Our version is about 85% the same as the reported question.

You are given a tree with treeNodes nodes labeled from 1 to treeNodes. For each index i, there is an undirected edge between nodes treeFrom[i] and treeTo[i]. Every edge has length 1, so the distance d(i, j) between two nodes is the number of edges on the path between them, and d(i, i) = 0.

You are also given an array a of length treeNodes, where a[j - 1] is the weight of node j.

The beauty of node i is the sum of d(i, j) * a[j - 1] over every node j in the tree.

Return the label of the node with the largest beauty. If several nodes share the largest beauty, return the smallest of their labels.

Function

findMaxBeautyNode(treeNodes: int, treeFrom: int[], treeTo: int[], a: int[]) → int

Examples

Example 1

treeNodes = 4treeFrom = [1,3,2]treeTo = [2,2,4]a = [4,3,2,1]return = 4

Node 2 is joined to nodes 1, 3 and 4. The beauties are:

  • Node 1: 0 * 4 + 1 * 3 + 2 * 2 + 2 * 1 = 9
  • Node 2: 1 * 4 + 0 * 3 + 1 * 2 + 1 * 1 = 7
  • Node 3: 2 * 4 + 1 * 3 + 0 * 2 + 2 * 1 = 13
  • Node 4: 2 * 4 + 1 * 3 + 2 * 2 + 0 * 1 = 15

Node 4 has the largest beauty, so the answer is 4.

Example 2

treeNodes = 3treeFrom = [1,2]treeTo = [2,3]a = [1,1,1]return = 1

The tree is the path 1 - 2 - 3. Node 1 has beauty 0 + 1 + 2 = 3, node 2 has 1 + 0 + 1 = 2, and node 3 has 2 + 1 + 0 = 3. Nodes 1 and 3 tie, so return the smaller label, 1.

Example 3

treeNodes = 1treeFrom = []treeTo = []a = [5]return = 1

With one node, every distance is 0, so node 1 has beauty 0 and is the answer.

Constraints

  • 1 <= treeNodes <= 2 * 10^4
  • treeFrom.length == treeTo.length == treeNodes - 1
  • 1 <= treeFrom[i], treeTo[i] <= treeNodes
  • The edges form a tree: all nodes are connected and there are no cycles.
  • a.length == treeNodes
  • 0 <= a[i] <= 10^4

More C3.ai interview questions

  • Drop Recent Duplicate MessagesOA · Seen Oct 2026
  • Maximum K-Star SumOA · Seen Oct 2026
  • Largest Square Sub-Grid Within a Sum LimitOA · Seen Jan 2023
  • Prefix Scores With the Running MaximumOA · Seen Jan 2023
  • Count Vowel Strings With Follow RulesOA · Seen Apr 2022
  • Photo Album Insert OrderOA · Seen Apr 2022
  • Sort by Frequency, Then ValueOA · Seen Apr 2022
  • Count Distinct Binary Search TreesOA · Seen Mar 2022
  • Count Palindromic Subsequences of Length KOA · Seen Mar 2022
  • Fewest Turns to Open a Wheel LockPHONE SCREEN · Seen Nov 2024

Similar questions at other companies

  • Minimum Leaf Path Sum over All RootsInfosys · OAInfosys interview questions
  • Maximum Strength of Every NeuronMicrosoft · OAMicrosoft interview questions
  • Maximum Reservoir PowerWells Fargo · OAWells Fargo interview questions
  • Sum of Weighted Distances in a TreeGoogle · ONSITE INTERVIEWGoogle interview questions
  • Distance Sums to Special Nodes in a Weighted TreeNutanix · ONSITE INTERVIEWNutanix interview questions
  • Part 2: Batch Access ReviewScale AI · OAScale AI interview questions
  • Sum Dynamic Weighted Tree DistancesJuspay · OA
  • Binary Tree CamerasAmazon · OA · PHONE SCREEN
  • Special Diameter EndpointsAgoda · OAAgoda interview questions
  • Tree PointsThe D.E. Shaw Group · OAThe D.E. Shaw Group interview questions

Interview reports that mention this question

  • C3.ai FDE and Other New Grad Roles: 5 Experiences (Part 2 of 2)

C3.ai interview experiences

  • C3.ai New Grad Interviews: 25 Experiences (Part 1 of 2)
  • C3.ai New Grad Forward Deployed Engineer Interview: 1 Experience
All C3.ai interview questionsSee C3.ai hiring insights
Saved
class Solution {
    public int findMaxBeautyNode(int treeNodes, int[] treeFrom, int[] treeTo, int[] a) {
        // Write your code here.
    }
}
Checking account…