BinaryTree Maximum Sum Path in JAVA

This is my implementation of the algorithm on finding the maximum sum path of a BinaryTree. The path does not have to start from the root node and does not have to end on a leaf node. The idea behind this algorithm is to store the path from the root node to the current node in an auxiliary structure such as an Array or ArrayList, check the aggregate sum of the list while iterating backward, and replacing the global max per iteration. The algorithm is implemented with pre-order traversal using a Stack to keep track of the parent nodes, and a second Stack to keep track of the level I am current on.

public static int findMaxSumPath(TreeNode root) {
    if (root == null) return 0;

    Stack<TreeNode> parents = new Stack<TreeNode>();
    Stack<Integer> levels = new Stack<Integer>();
    List<Integer> path = new ArrayList<Integer>();

    TreeNode cur = root;
    int level = 0;
    int max = Integer.MIN_VALUE;

    while (!parents.isEmpty() || cur != null) {
        if (cur != null) {
            if (level < path.size())
                path.set(level, cur.data);
            else
                path.add(cur.data);

            int sum = 0;
            for (int i = level; i >= 0; i--) {
                sum += path.get(i);
                max = Math.max(max, sum);
            }

            parents.push(cur);
            levels.push(level++);
            cur = cur.left;
        }
        else {
            TreeNode parent = parents.pop();
            level = levels.pop();

            if (parent.right != null) level++;
            cur = parent.right;
        }
    }

    return max;
}

This article is my 15th oldest. It is 224 words long, and it’s got 0 comments for now.