Type error: unpacking tuples Recursive function call-CodePudding

I have the following piece of code:

def myCalculation(self, root, max_val): 
        
        if root == None:
            return -1
        
        LH = 1   (self.myCalculation(root.left, max_val))[0]
        RH = 1   (self.myCalculation(root.right, max_val))[0]
        
        ret = LH RH
        
        if max_val < ret:
            max_val = ret
            
        return (max(LH, RH), max_val)

Here, I return two values because for the last function call on stack to exit the function must return the max_val to the calling function. So, when at the 3rd and 4th executable lines of the function I make a function call and try to use the return values, it gives TypeError desribed just below.

The error is :

> TypeError: 'int' object has no attribute '__getitem__'

Full traceback:

TypeError: 'int' object has no attribute '__getitem__'
    LH = 1   (self.myCalculation(root.left, max_val))[0]
Line 14 in myCalculation (Solution.py)
    LH = 1   (self.myCalculation(root.left, max_val))[0]
Line 14 in myCalculation (Solution.py)
    LH, max_val1 = 1   self.myCalculation(root.left, 0)
Line 32 in diameterOfBinaryTree (Solution.py)
    ret = Solution().diameterOfBinaryTree(param_1)
Line 67 in _driver (Solution.py)
_driver()

Line 77 in (Solution.py)

I cannot quite figure what the problem is with packing and unpacking tuples in recursion?

CodePudding user response：

The base case:

if root == None:
   return -1

returns an integer, which you can't call __getitem__ on, as the error message indicates.

If I'm reading your code right, it looks like you wouldn't use the second value in a returned tuple for the base case. So, you can do something like:

if root == None:
   return -1, None

CodePudding user response：

The issue is your base case returns a single value. However, you can simplify your algorithm by removing the need to return multiple values and the extra parameter, max_val. We can calculate the diameter of a tree, t -

def diameter(t):
  if not t:
    return 0
  else:
    return max(                            # return maximum of:
      diameter(t.left),                    # diameter of left
      diameter(t.right),                   # diameter of right
      1   height(t.left)   height(t.right) # or diameter of t itself
    )

Where height of a tree, t, is defined as -

def height(t):
  if not t:
    return 0
  else:
    return 1   max(height(t.left), height(t.right))

You can write myCalculation in your Solution class -

class Solution:
  def myCalculation(self, root):
    return diameter(root)

Because height will be called multiple times on child nodes, this program can be optimized using lru_cache, effectively "memoizing" the function -

from functools import lru_cache

@lru_cache
def height(t):
  # ...