Part of Microsoft
Engaged Employer
LinkedIn Interview Question
Implement a function to compute the maximum sum of any downward path in a tree represented by a parent array and node values.
Interview Answer
Anonymous
Sep 8, 2025
I designed a DFS-based recursive solution to traverse the tree, maintaining a global maximum path sum. Built an adjacency list to represent the tree. Used recursion to compute the max downward path sum from each node. Updated a global maximum at every node. Achieved O(n) time complexity. The solution passed all test cases.