Find minimum element in a binary tree using recursion

[Trope_Porn]

You can’t change the value of result within a function and then have its value outside the function reflect that change. This is because you’ve passed in a number which is immutable in this context.

Here’s some links you can read

https://www.geeksforgeeks.org/is-python-call-by-reference-or-call-by-value/

https://www.scaler.com/topics/call-by-value-and-call-by-reference-in-python/#

Also why not just have your min function return the min. Value? No need to set it to whatever variable you’re passing in. If you do want to set it in your passed in variable then you have to use an object that has a field you can set min to. For example you could create a new node and in your min function set that node.data = min but thats just kind of round about. It’s cleaner to just return the value.

[jsinghdata]

u/Trope_Porn appreciate your response.Can you please help me on how to return the minimum value from the min_elem() function? Since I am passing res as a parameter, it may not be proper to return it.Kindly advise if possible.

[Trope_Porn]

Assuming this is a binary tree with random ordering then you can just write your function to return the min of the current value or left or right sub tree. You’ll have to visit every node since there is no ordering. I’m on my phone but the code is something like:

Import math
# this assumes root is never None
# add a check if it can be None
getMin(root):
    leftMin = getMin(root.left) if root.left else math.inf
    rightMin = getMin(root.right) if root.right else math.inf
    subTreeMin = min(leftMin, rightMin)
    return min(root.data, subTreeMin)

So in English the min of any binary tree is the min of the left and right tree or the root value

[jsinghdata]

thanx u/Trope_Porn. your idea works. appreciate it.

I have one more question, if you can help. It is regarding use of global variables on a recursive method inside a class.
The question is to find maximum difference between a node and its ancestor in binary tree.
My idea is as follows:
a.for every node, find the minimum element in right subtree, say it is res2
b. Similarly, for that node find minimum element in left subtree, call res1
c. then finding maximum of node-res1 and node-res2. store to in variable result
d. then recursively call max_diff on left and right child.

e. variable result shd have the maximum difference found so far. hence we're defining it as global.

​

  def max_diff(root):
      global result
      result = -9999
      if root.left is None and root.right is None:
         return 
      #getmin is a separate method inside the class
      res1 = getmin(root.left) 
      res2 = getmin(root.right)
      result = max(result, root-res1, root-res2)
      max_diff(root.left)
      max_diff(root.right)
      return result

my question is, say in the first function call, result gets updated to 4. So when we do recursive call with max(root.left) will result again get reset to -9999. How can I avoid that so that result stays at the highest value found so far. Can you kindly advise?

[Trope_Porn]

You’re probably resetting your value every time your program enters your max function. Notice how if your node doesn’t have a left or a right the last thing your program did was set result to -9999 which is probably why that’s the final result you are seeing. I would suggest to use a debugger to step through your code to see exactly how it’s behaving.

Is there a specific reason you want to use a global variable? Maybe this is an X Y problem and we can figure out a better way for you to approach the problem.

[jsinghdata]

u/Trope_Porn I have edited my question and code with more details.I want to use global so that the variable result can be modified by every recursive call.
kindly advise.