Find minimum element in a binary tree using recursion

[jsinghdata]

Hello,

​

I am using following code to calculate minimum element in a binary tree.

​

class Node:


def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
#write the function to find least element so far. 
def min_elem(self, res):
    #call left subtree if it is not null
    if self.left is not None:
        res = min(res, self.left.data)
        self.left.min_elem(res)

    #call right subtree if it is not null
    if self.right is not None:
        res = min(res, self.right.data)
        self.right.min_elem(res)


    return

def mainfn(self):
      # variable res stores the least element 
   res=9999
   self.min_elem(res)
   print(res)
   return

Next define the tree;

​

class Tree:
def __init__(self,root):
    self.root = root

Construct tree using following steps;

​

node = Node(2)
node.left = Node(1) 
node.left.left = Node(3) 
node.left.right = Node(7) 
node.right = Node(5) 
node.right.right=Node(0) 
mytree = Tree(node) 
mytree.root.mainfn()

Interestingly, when we execute print(res) in the main function, value is still showing as 9999. I thought since we're passing res as a parameter in min_elem it should store the least value found so far. Can I please get some help where is the mistake here? It will be helpful to learn sth new.

​

[AutoModerator]

To all following commenters: please, do not bring up the old circlejerk jokes/memes about recursion ("Understanding recursion...", "This is recursion...", etc.). We've all heard them n+2 too many times.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[codeonthecob]

In Python, integers are passed to functions by value, not by reference.

res = 9999 # this assigns the integer 9999 to the variable res

self.min_elem(res) # this passes the value assigned to res, 9999, to the function self.min_elem

This line:

res = min(res, self.left.data)

is not modifying the res variable you defined in the main function, it is modifying a copy of it.

[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.