Created
April 3, 2020 12:39
-
-
Save jatinsharrma/c634bf4fe62c95406663864644421bb8 to your computer and use it in GitHub Desktop.
BInary Tree branch sum
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
''' | |
Write a function that takes in a binary tree and returns a list of its branch sums | |
(ordered from the sum of the left branch to the sum of the branch at right). | |
A branch sum is the sum of all values within a branch of the Binary Tree. | |
A branch of a Binary Tree is a path in a tree that begins at the root node and ends at any leaf node. | |
''' | |
#This class makes a node | |
class Node: | |
def __init__(self,value): | |
self.right = None | |
self.left = None | |
self.value = value | |
#this method sets Right child of current node | |
def setRight(self,right): | |
self.right = right | |
#this method sets Left child of current node | |
def setLeft(self, left): | |
self.left = left | |
#this method returns Right child of current node | |
def getRight(self): | |
return self.right | |
#this method return Left child of current node | |
def getLeft(self): | |
return self.left | |
#this method returns value of current node | |
def getValue(self): | |
return self.value | |
# This class makes a binary serach tree | |
class BT: | |
def __init__(self): | |
self.root = None | |
# this method returns root of bianry tree | |
def getRoot(self): | |
return self.root | |
# this method inserts a node in binary tree | |
def insert(self,value): | |
if self.root is None: | |
node = Node(value) | |
self.root = node | |
else: | |
node = [self.root] | |
while len(node) != 0: | |
current_node = node.pop(0) | |
if current_node.getLeft() is None: | |
current_node.setLeft(Node(value)) | |
break | |
elif current_node.getRight() is None: | |
current_node.setRight(Node(value)) | |
break | |
else: | |
node.append(current_node.getLeft()) | |
node.append(current_node.getRight()) | |
#method finds sum of all branches recursiverly | |
def sum(self,root,total_sum,sum_list): | |
if root is None: | |
return | |
total_sum += root.getValue() | |
self.sum(root.getRight(),total_sum,sum_list) | |
self.sum(root.getLeft(),total_sum,sum_list) | |
if root.getLeft() is None and root.getRight() is None: | |
sum_list.append(total_sum) | |
# values to be inserted | |
items = [1,2,3,4,5,6,7,8,9,10] | |
#making object of Binary Tree | |
bst = BT() | |
# inserting values | |
for i in items: | |
bst.insert(i) | |
# sum of all branches will be saved into this list | |
sum_list = [] | |
# calling sum function | |
bst.sum(bst.getRoot(),0,sum_list) | |
#printing sum_list | |
print(sum_list[::-1]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment