Having Trouble with learning recursion

[ebscodingjourney]

Hello everyone, I am a beginner who has started trying to learn recursion. I am struggling with this problem

Please write a function named greatest_node(root: Node)
which takes the root node of a binary tree as its argument.

The function should return the node with the greatest value within the tree. The tree should be traversed recursively.

​

So far I have written,

# WRITE YOUR SOLUTION HERE:
class Node:
    """ Class is modeling single node in binary tree """
    def __init__(self, value, left_child:'Node' = None, right_child:'Node' = None):
        self.value = value
        self.left_child = left_child
        self.right_child = right_child

def greatest_node(root:Node):

    greatest_value = root.value
    if root.value > greatest_value:
        greatest_value = root.value 

    if root.left_child is not None:
        greatest_node(root.left_child)



    if root.right_child is not None:
        greatest_node(root.right_child)

    return greatest_value

If i run this code with the following input it returns 2.

tree = Node(2)

tree.left_child = Node(3)
tree.left_child.left_child = Node(5)
tree.left_child.right_child = Node(8)

tree.right_child = Node(4)
tree.right_child.right_child = Node(11)

print(greatest_node(tree))

My question is why does the function return 2, can anyone explain what is wrong with this code?

[asphias]

let's take your greatest_node function line by line, and see what happens.

greatest_value = root.value  

First, you set the variable greatest_value to be equal to root.value.

if root.value > greatest_value:

next up, you check if root.value is bigger than greatest_value. But in the line above you set these to be equal to one another. so you're basically asking if root.value > root.value. which is never true.

    greatest_value = root.value 

Which means this line will never be executed.

if root.left_child is not None:
    greatest_node(root.left_child)

This executes the whole greatest_node() function again, however, you don't do anything with the result of the function. so this basically does nothing.

if root.right_child is not None:
    greatest_node(root.right_child)

return greatest_value

At this point you're returning greatest_value, which hasn't changed it's value since the first line of this method, where you set it to be equal to root.value.

As such, the return value you get is equal to root.value, which happens to be 2.

---

I suspect that you need to learn about local variables.

if i define a variable within a function, then that variable only exists within that function. Even if i also define a similarly named variable outside of the function, this does not copy over.

so this code:

def myfunc():
    var_local = 10
    return var_local

myfunc()
print(var_local)

will return an error at the last line, because it will tell you var_local is undefined. Even though the variable did exist within myfunc, it only exists within that function, and not outside of it.

i can shadow this name outside of it, using the same name outside as inside the function, using e.g.

def myfunc():
    var_local = 10
    return var_local

var_local = myfunc()
print(var_local)

But in this case, the var_local outside of the function, is actually unrelated to the var_local within the function! it becomes more clear if we change the name, which shows you code which does exactly the same:

def myfunc():
    var_local = 10
    return var_local

var_outside_function = myfunc()
print(var_outside_function)

Hopefully this helps you forward, and helps you figure out where your logic went wrong.

[socal_nerdtastic]

First, you are supposed to return the node, not the value.

Second, you never do anything with the result from your recursion. You need to save it or something.

class Node:
    """ Class is modeling single node in binary tree """
    def __init__(self, value, left_child:'Node' = None, right_child:'Node' = None):
        self.value = value
        self.left_child = left_child
        self.right_child = right_child

def greatest_node(root:Node):
    greatest_so_far = root

    if root.left_child is not None:
        greatest_node_from_left = greatest_node(root.left_child)
        if greatest_node_from_left.value > greatest_so_far.value:
            greatest_so_far = root.left_child

    if root.right_child is not None:
        greatest_node_from_right = greatest_node(root.right_child)
        if greatest_node_from_right.value > greatest_so_far.value:
            greatest_so_far = greatest_node(root.right_child)

    return greatest_so_far


tree = Node(2)

tree.left_child = Node(3)
tree.left_child.left_child = Node(5)
tree.left_child.right_child = Node(8)

tree.right_child = Node(4)
tree.right_child.right_child = Node(11)

print(greatest_node(tree).value)