Stuck on Recursive State Design for a Zigzag Alternating-Sum Path in a Binary Tree

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?

I've spent some time trying to fix the logic of your code, but I haven't been able to (that's how incapable I am), so I can only show you a different way to achieve the result.

int max = 0;

void maxZigZagSum( Node root, int value, boolean sum ) {
   if( root != null ) {
      if( sum ) {
          value += root.value;
      }
      else  {
         value -= root.value;
      }
      maxZigZagSum( root.left, value, ! sum );
      maxZigZagSum( root.right, value, ! sum );
   }
   else {
      if( value > max ) {
         max = value;
      }
   }
}

I think the code is self-explanatory. If the node turns out to be null, we update (if applicable) the value of max. If it is not null, we update the value of value based on the state of sum, and we recursively apply this to both children, inverting the value of sum.

This is the code I implemented for testing purposes:

class Node {

   Node( int val, Node lef, Node rig ) {
      value = val;
      left = lef;
      right = rig;
   }
   int value;
   Node left, right;
}

void init() {
   Node root = new Node( 0,
           new Node( 1, new Node( 3, null, null ), new Node( 2, null, null ) ),
           new Node( 4, new Node( 5, null, null ), new Node( 6, null, null ) )
   );
   maxZigZagSum( root, 0, true );
   System.out.println( max );
}