CODEWITHSUNDEEP
python
tibetish
tibetish

Reputation: 119

Binary tree: how to change every leaf value to the sum of the path to it

I'm trying to change the leaves' values to the sums of the paths to them (without returning anything). I tried using recursion, however I'm not sure at which point in the code I should call the set function and how to make sure it only changes the leaves . This is what I've tried so far:

class Node:

    def __init__(self, value, left=None, right=None):
        self.__value = value
        self.__left = left
        self.__right = right

    def get_left(self):
        return self.__left

    def get_right(self):
        return self.__right

    def get_value(self):
        return self.__value

    def set_value(self, value):
        self.__value = value


def sum_to_leaves(node):
    if node is None:
        return
    new_value = node.get_value() + sum_to_leaves(node.get_left()) + sum_to_leaves(node.get_right())
    if node.get_left() is None and node.get_right() is None:
        node.set_value(new_value)
        return

Upvotes: 0

Views: 264

Answers (1)

Kelly Bundy
Kelly Bundy

Reputation: 27609

Compute the path sum on your way down, passing it as parameter.

def sum_to_leaves(node, path_sum=0):
    if node:
        path_sum += node.get_value()
        sum_to_leaves(node.get_left(), path_sum)
        sum_to_leaves(node.get_right(), path_sum) 
        if node.get_left() is node.get_right():
            node.set_value(path_sum)

Upvotes: 1

Related Questions