Leetcode 1372: Why do these two code snippets give different results?

Question

I am solving LeetCode problem 1372. Longest ZigZag Path in a Binary Tree:

You are given the root of a binary tree.

A ZigZag path for a binary tree is defined as follow:

• Choose any node in the binary tree and a direction (right or left).

• If the current direction is right, move to the right child of the current node; otherwise, move to the left child.

• Change the direction from right to left or from left to right.

• Repeat the second and third steps until you can't move in the tree.

Zigzag length is defined as the number of nodes visited - 1. (A single node has a length of 0).

Return the longest ZigZag path contained in that tree.

The following is an accepted solution:

# Definition for a binary tree node.

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.longest_path = 0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        val1 = 1 + self.helper(root.right, 'r')
        val2 = 1 + self.helper(root.left, 'l')
        # print(val2, self.longest_path)
        val = max(val1, val2)
        return max(val, self.longest_path) - 1

    def helper(self, root, d):
        if root == None:
            return 0
        if d == 'l':
            l_path = 1 + self.helper(root.left, d='l')
            self.longest_path = max(self.longest_path, l_path)
            return 1 + self.helper(root.right, d='r')
        if d == 'r':
            r_path = 1 + self.helper(root.right, d='r')
            self.longest_path = max(self.longest_path, r_path)
            return 1 + self.helper(root.left, d='l')

Then I wanted to reduce the code a bit and pass the expression assigned to l_path directly as argument to max:

class Solution:
    def __init__(self):
        self.longest_path = 0

    def longestZigZag(self, root: Optional[TreeNode]) -> int:
        val1 = 1 + self.helper(root.right, 'r')
        val2 = 1 + self.helper(root.left, 'l')
        # print(val2, self.longest_path)
        val = max(val1, val2)
        return max(val, self.longest_path) - 1

    def helper(self, root, d):
        if root == None:
            return 0
        if d == 'l':
            self.longest_path = max(self.longest_path, 1 + self.helper(root.left, d='l'))
            return 1 + self.helper(root.right, d='r')
        if d == 'r':
            r_path = 1 + self.helper(root.right, d='r')
            self.longest_path = max(self.longest_path, r_path)
            return 1 + self.helper(root.left, d='l')

The only change is this line:

self.longest_path = max(self.longest_path, 1 + self.helper(root.left, d='l'))

My question:

The altered version returns different results. Why is that?

For instance, for this input the second version returns 1 (wrong) while the first version returns 2 (correct):

        1
       /
      1
     /
    1
   /
  1
   \
    1

Encoded format for this input on HackerRank: [1,1,null,1,null,1,null,null,1]

Answer 1

The reason for the difference is the order of execution of the following two expressions:

1. 1 + self.helper(root.left, d='l')
2. self.longest_path

helper can assign a new value to self.longest_path, so it matters whether you read self.longest_path before or after the call of self.helper -- the order of evaluation is important.

When avoiding the assignment to l_path, you can still get the correct order of execution by swapping the arguments passed to max.

This will give the correct result:

self.longest_path = max(1 + self.helper(root.left, d='l'), self.longest_path)
#                       ---------------------------- swapped ---------------