Given such a BST, you are asked to compute the sum along each
branch from root to a leaf node starting with the leftmost branch
and moving on to the rightmost.
The example below will clarify the problem.
Consider the BST below as input:
- Consider A Binary Search Tree Bst Whose Keys Are Numbers Given Such A Bst You Are Asked To Compute The Sum Along Eac 1 (37.11 KiB) Viewed 31 times
Note:
Your algorithm should work in time that is linear in the number
of nodes of the tree.
For your convenience, we will reuse the binary search tree data
structure class TreeNode with functions for insertion from the
previous problem. Please ensure that you have run the cell
corresponding to that problem.
Please complete the implementation of the sumOfBranches
function. Note, coding language is python
def sumOfBranches(root_node):
# return a list of sums
# your code here
To check for correctness
def make_tree(insertion_list):
assert len(insertion_list) > 0
root_node = TreeNode(insertion_list[0])
for elt in insertion_list[1:]:
root_node.insert(elt)
return root_node
print('-- Test 1 --')
# Same as the example from problem 1
tree1 = make_tree([11, 18, 15, 13, 21, 17, 4])
lst1 = sumOfBranches(tree1)
print(lst1)
assert lst1 == [15, 57, 61, 50]
print('-- Test 2 --')
# Same as example from problem 2
tree2 = make_tree([11,4, 18, -1, 7, 15, 21, 2, 13, 17])
lst2 = sumOfBranches(tree2)
print(lst2)
assert lst2 == [16, 22, 57, 61, 50]
print('-- Test 3 --')
tree3 = make_tree([15])
lst3 = sumOfBranches(tree3)
print(lst3)
assert lst3 == [15]
print('-- Test 4 --')
tree4 = make_tree([4, 1, 2, 3, 8, 5, 6, 7, 10, 9])
lst4 = sumOfBranches(tree4)
print(lst4)
assert lst4 == [10, 30, 31]
print('All tests passed: 15 points!')
-1 2 4 7 13 11 15 18 17 21