ARTICLE AD BOX
I’m trying to reason about a recursive algorithm on trees and I feel like I’m missing something subtle.
I have an immutable binary tree (not a BST) where each node has an int value. I want to compute the maximum alternating-sum zigzag path anywhere in the tree. A path is any downward path (start at any node, go only to children). The path must strictly alternate left/right at each step. The sum alternates signs starting with + at the starting node: +v0 − v1 + v2 − v3 …. Single-node paths are allowed.
Here’s the code I thought should work, but it fails on some cases with negative values and when the best path doesn’t start at the root.
int maxZigZagSum(Node root) { return helper(root, true, 0); } int helper(Node node, boolean goLeft, int sign) { if (node == null) return 0; int cur = (sign == 0 ? node.val : -node.val); int next; if (goLeft) { next = helper(node.left, false, 1 - sign); } else { next = helper(node.right, true, 1 - sign); } return Math.max(cur, cur + next); }I tried calling helper twice at the root (once starting left, once right), but that still doesn’t fix all cases. Intuitively, I feel like I need to track both “last direction” and “parity of the sum”, but whenever I add more parameters the recursion explodes and I can’t keep it O(n). I also don’t see how to handle paths that start in the middle of the tree without restarting recursion from every node, which would be O(n²).
What minimal information needs to be returned from each recursive call so that the parent can combine results correctly? How do you structure the recursion so that paths can start at any node, but you still only traverse the tree once? Why doesn’t the “return the best path starting here” approach work without additional state?
