Node With Maximum Subtree Sum

I/P:

20

10 20 -50 -1 60 -1 -1 30 -70 -1 80 -1 90 -1 -1 40 -100 -1 -1 -1

O/P:  30@130

Returning something else & need to calculate something else.

package pep.Day31;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Stack;

public class Node_With_Maximum_Subtree_Sum {
    private static class Node {
        int data;
        ArrayList<Node> children = new ArrayList<>();
    }

    public static Node construct(int[] arr) {
        Node root = null;
        Stack<Node> st = new Stack<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == -1) {
                st.pop();
            } else {
                Node t = new Node();
                t.data = arr[i];

                if (st.size() > 0) {
                    st.peek().children.add(t);
                } else {
                    root = t;
                }
                st.push(t);
            }
        }

        return root;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        String[] values = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(values[i]);
        }
        Node root = construct(arr);

        nodeWithMaximumSubtreeSum(root);
        System.out.println(maxSumNode + "@" + maxSum);
    }

    static int maxSum = Integer.MIN_VALUE;
    static int maxSumNode = 0;

    public static int nodeWithMaximumSubtreeSum(Node node) {
        int sum = 0;
        for (Node child : node.children) {
            sum += nodeWithMaximumSubtreeSum(child);
        }

        sum += node.data;
        if (maxSum < sum) {
            maxSum = sum;
            maxSumNode = node.data;
        }

        return sum;
    }

}

Time Complexity: We are visiting each node exactly once, hence the total time complexity will be O(n) where n = number of nodes in the tree.

Space Complexity: We are just taking two integer variables mSum and mSumNode to find the maximum subtree sum. Hence, we are taking O(1) auxiliary space. However, again, due to recursion, the recursion call stack will take up O(d) space where d = maximum depth of the tree.