Closest leaf node solution not returning

Question

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

def minimumDistanceHelper(root, node, closest):
    if(root is None):
        return
    
    if(root.left is None and root.right is None):
        if(abs(closest-node.key)>abs(node.key-root.key)):
            closest = root.key
            print("closest:", closest)
        
    else:
        minimumDistanceHelper(root.left, node, closest)
        minimumDistanceHelper(root.right, node,closest)

def minimumDistance(root, node):
    if(root is None):
        return float('inf')
    closest = root.key
    minimumDistanceHelper(root, node, closest)
    return closest

# Driver Code 
if __name__ == '__main__': 

    # Let us create Binary Tree shown 
    # in above example  
    root = newNode(10)  
    root.left = newNode(12)  
    root.right = newNode(13)  

    root.right.left = newNode(14)  
    root.right.right = newNode(15)  

    root.right.left.left = newNode(21)  
    root.right.left.right = newNode(22)  
    root.right.right.left = newNode(23)  
    root.right.right.right = newNode(24)  

    root.right.left.left.left = newNode(1)  
    root.right.left.left.right = newNode(2)  
    root.right.left.right.left = newNode(3)  
    root.right.left.right.right = newNode(4)  
    root.right.right.left.left = newNode(5)  
    root.right.right.left.right = newNode(6)  
    root.right.right.right.left = newNode(7)  
    root.right.right.right.right = newNode(8)  

    x = root.right  

    print("The closest leaf to the node with value", x.key, "is at a distance of",  minimumDistance(root, x))

I want to print closest leaf node to a particular node in a binary tree. I am getting the correct answer in the function defined but I am not able to return that answer. Link to question: https://www.geeksforgeeks.org/closest-leaf-to-a-given-node-in-binary-tree/

what is the expected output? Currently your code returns `10` for me — M Z, Aug 21 '20 at 16:53
Your program outputs more than a single number. What is the expected output? — quamrana, Aug 21 '20 at 17:15

score 1 · Answer 1 · answered Aug 21 '20 at 17:39

You're trying to pass "closest" by reference, but arguments in Python are passed by assignment. Relevant SO answer, official Python FAQ.

You have (lines snipped for brevity):

def minimumDistanceHelper(root, node, closest):
    closest = root.key
    print("closest:", closest)

def minimumDistance(root, node):
    closest = root.key
    minimumDistanceHelper(root, node, closest)
    return closest

When you pass closest to minimumDistanceHelper, since closest is an immutable integer, the closest parameter inside of minimumDistanceHelper does not refer to the same object as the closest declared inside of the minimumDistance function. As a result, the return value for minimumDistance is always root.key.

There are two ways you could get around this. The better way is to return the value of closest from minimumDistanceHelper. The end of minimumDistanceHelper would become something like

closestLeft = minimumDistanceHelper(root.left, node)
closestRight = minimumDistanceHelper(root.right, node)
if abs(closestLeft - node) < abs(closestRight - node):
    return closestLeft
else:
    return closestRight

The other way would be to convert closest into a mutable type, like a list or a dict. If you insisted on doing it this way, you could declare closest as

closest = [root.key]

then write to it inside of minimumDistanceHelper with

closest[0] = root.key

But note how this writes to the 0th index of closest, not closest itself. If you were to use

closest = [root.key]

we would have the same problem and the new closest would not be the original version.

Err, no. Arguments are passed by reference, not by value. However, assignment to a variable does nothing to the object referred to. Mandatory link to [Ned Batchelder](https://nedbatchelder.com/text/names.html) — quamrana, Aug 21 '20 at 19:32
[This](https://www.learncpp.com/cpp-tutorial/73-passing-arguments-by-reference/) is what pass-by-reference means to me, but [apparently](https://stackoverflow.com/questions/373419/whats-the-difference-between-passing-by-reference-vs-passing-by-value) there's disagreement about what these terms mean. — Elliot Way, Aug 23 '20 at 13:40

Closest leaf node solution not returning

1 Answers1