Can't get global variable of DFS in Python to return the right value-CodePudding

I am learning to use Python to implement DFS algorithm. The DFS will return the max value in a binary tree

There are 2 approaches I wrote. The 1st approach is findMax function - it uses return values to track the max value in a tree. The 2nd approach is findMax2 function - it uses a global variable to track the max value.

I googled around, but couldn't really understand why my 2nd approach doesn't work - the global variable, max_val, won't return the correct value, and the error msg is

UnboundLocalError: local variable 'max_val' referenced before
assignment

I'm not very good at Python, so any help is greatly appreciated. :) Here is the code.

class Node:
  def __init__(self, key):
    self.left = None
    self.val = key
    self.right = None

  def inorder(self, root):
    if root:
      self.inorder(root.left)
      print(root.val)
      self.inorder(root.right)

  def findMax(self, root):
    if root is None:
      return float('-inf')  
    max_lv = self.findMax(root.left)       
    max_rv = self.findMax(root.right)
    return max(root.val, max_lv, max_rv)    

  max_val = float('-inf')
  def findMax_2(self, root):
    if root is None:
      return max_val
    max_val = max(max_val, root.val)    
    dfs(root.left)                      
    dfs(root.right)

r = Node(5)
r.left = Node(1)
r.left.left = Node(8)
r.left.right = Node(11)
r.inorder(r)
print(r.findMax_2(r))

Update: Thanks for everyone's comments. I modified my code based on ggorlen's suggestion.

def findMax_2(self, root):
    def dfs(node):
      if node is None:
        return max_val
      max_val = max(max_val, node.val)
      print("max_val:", max_val)
      dfs(node.left)
      dfs(node.right)

    max_val = float('-inf')
    dfs(root)
    return max_val

But I still got the same error:

Traceback (most recent call last):
  File "dfs_findMax_2.py", line 56, in <module>
    print("max val:", r.findMax_2(r))
  File "dfs_findMax_2.py", line 44, in findMax_2
    dfs(root)
  File "dfs_findMax_2.py", line 38, in dfs
    max_val = max(max_val, node.val)
UnboundLocalError: local variable 'max_val' referenced before assignment

Did I miss anything?

CodePudding user response：

Python scoping rules have a few sharp corners.

In the class and outside the function, max_val is a class variable. Inside the function it is a lexical variable scoped to the function, which just happens to have the same name. Your error is because you are accessing the lexical variable before it is assigned to, so Python knows you are confused (but didn't give enough context to unconfuse you).

To access the class variable inside the function you need to access self.max_val.

If it was truly a global variable, you'd need to have a global max_val declaration in the function before you do anything with it. (It isn't, so don't try it.) And in the case of one function inside another, you'd need to do a nonlocal max_val instead.

And, finally, because it is a class variable, it will be accessible through all instances of the class. If you wanted it to be an instance variable instead, you'd have assigned to self.max_val inside of your init method, and you'd still access it through self.max_val in other methods.

CodePudding user response：

Based on ggorlen's advice, here is the code that works. Thank you!

def findMax_2(self, root):
    def dfs(node):
        nonlocal max_val
        if node is None:
            return
        max_val = max(max_val, node.val)
        dfs(node.left)
        dfs(node.right)

    max_val = float('-inf')
    dfs(root)
    return max_val