CODEWITHSUNDEEP
pythonpython-requestsbinarysumbinary-search-tree
gmanread
gmanread

Reputation: 33

How to compute the sum and the total number of nodes in a Binary Search Tree?

I am trying to figure out a way to compute the sum and the total number of nodes in a BST, Binary Search Tree. I assume that the values of the nodes are all numerical. I have made the following code and tried different ways, but everything leads up to missing root or similar missing things.

class BinarySearchTree:
    def __init__(self, value=None):
        self.value = value
        if self.value:
            self.left_child = BinarySearchTree()
            self.right_child = BinarySearchTree()
        else:
            self.left_child = None
            self.right_child = None

    def is_empty(self):
        return self.value is None

    def insert(self, value):
        if self.is_empty():
            self.value = value
            self.left_child = BinarySearchTree()
            self.right_child = BinarySearchTree()

        elif value < self.value:
            self.left_child.insert(value)

        elif value > self.value:
            self.right_child.insert(value)

    def compute_sum(self):
        #Here I should make a function to compute the sum of all the node values in the BST. 
        return "Not Implemented"


    def compute_count(self):
        #Here I should make a function to compute the total number of nodes in the BST. 
        return "Not Implemented"

def main():
    my_tree = BinarySearchTree()

    my_tree.insert(2)
    my_tree.insert(4)
    my_tree.insert(6)
    my_tree.insert(8)
    my_tree.insert(10)

    print('sum:', my_tree.compute_sum())
    print('number of nodes:', my_tree.compute_count())

if __name__ == "__main__":
    main()

please no hate (: Everyone has been a beginner before.

Upvotes: 0

Views: 263

Answers (1)

DarrylG
DarrylG

Reputation: 17156

Update code to the following.

class BinarySearchTree:
    def __init__(self, value=None):
        self.value = value
        if self.value:
            self.left_child = BinarySearchTree()
            self.right_child = BinarySearchTree()
        else:
            self.left_child = None
            self.right_child = None

    def is_empty(self):
        return self.value is None

    def insert(self, value):
        if self.is_empty():
            self.value = value
            self.left_child = BinarySearchTree()
            self.right_child = BinarySearchTree()

        elif value < self.value:
            self.left_child.insert(value)

        elif value > self.value:
            self.right_child.insert(value)

    def compute_sum(self):
        ' compute the sum of all the node values in the BST '
        if self.value is None:
            return 0         # No nodes
        else:
            # current plus sum of child nodes
            return self.value + self.left_child.compute_sum() + self.right_child.compute_sum()


    def compute_count(self):
        ' compute the total number of nodes in the BST ' 
        if self.value is None:
            return 0  # No nodes
        else:
            # One for current plus count of child nodes
            return 1 + self.left_child.compute_count() + self.right_child.compute_count()

def main():
    my_tree = BinarySearchTree()

    my_tree.insert(2)
    my_tree.insert(4)
    my_tree.insert(6)
    my_tree.insert(8)
    my_tree.insert(10)

    print('sum:', my_tree.compute_sum())
    print('number of nodes:', my_tree.compute_count())

if __name__ == "__main__":
    main()

Upvotes: 1

Related Questions