0

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?

LED Fantom
  • 1,229
  • 1
  • 12
  • 32
  • 1
    what output are you getting? – BhusalC_Bipin Jun 09 '22 at 00:17
  • 1
    Looks like `UnboundLocalError: local variable 'max_val' referenced before assignment`. Is that the output OP gets too? Anyway, the class variable is a worse way to write this, so just use the existing one. If you do want to do this, use an inner function and scope `max_val` to the outer function. Also, I suggest using 4 space indentation so others can read your code easily. 2 space indentation is only understandable in languages with braces or `end` keywords for blocks. – ggorlen Jun 09 '22 at 00:30
  • `findMax_2` doesn't `return` anything unless `root` is `None`, which isn't the case for the top-level call in the `print` statement. – user3386109 Jun 09 '22 at 01:01
  • always put full error message (starting at word "Traceback") in question (not in comments) as text (not screenshot, not link to external portal). There are other useful information. – furas Jun 09 '22 at 02:05
  • @ggorlen Could you take a look at my updated code? Not sure what I missed, but still got the same error. – LED Fantom Jun 09 '22 at 02:06
  • 1
    Try `nonlocal max_val` at the top of the inner function. There's no point in `return max_val` since you're ignoring the return value. – ggorlen Jun 09 '22 at 02:10
  • @ggorlen Trying `nonlocal` is a reasonable guess, but that isn't going to work either. See my answer. – btilly Jun 09 '22 at 02:17
  • No problem, though this should probably be closed as a dupe of [Python nested functions variable scoping](https://stackoverflow.com/questions/5218895/python-nested-functions-variable-scoping) at this point. I already burned my vote. – ggorlen Jun 09 '22 at 02:39

2 Answers2

2

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.

btilly
  • 43,296
  • 3
  • 59
  • 88
0

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
LED Fantom
  • 1,229
  • 1
  • 12
  • 32
  • This works because by making `dfs` an inner function now `max_val` *is* a `nonlocal` variable. – btilly Jun 09 '22 at 15:19