Skip to content

Instantly share code, notes, and snippets.

@jatinsharrma
Created April 3, 2020 12:39
Show Gist options
  • Save jatinsharrma/c634bf4fe62c95406663864644421bb8 to your computer and use it in GitHub Desktop.
Save jatinsharrma/c634bf4fe62c95406663864644421bb8 to your computer and use it in GitHub Desktop.
BInary Tree branch sum
'''
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