1. Branch Sums
Python
# This is the class of the input root. Do not edit it.
class BinaryTree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
## O(N) time | O(N) space (because return haft of the leaf nodes, thereforem 1/2N => N)
def branchSums(root):
# Write your code here.
sums = []
calculateBranchSums(root, 0, sums)
return sums
def calculateBranchSums(node, runningSum, sums):
if node is None:
return
newRunningSum = runningSum + node.value
## if a leaf node, we gonna add sum into sums[]
if node.left is None and node.right is None:
sums.append(newRunningSum)
return
# if not a leaf node, we continue to sum child nodes
calculateBranchSums(node.left, newRunningSum, sums)
calculateBranchSums(node.right, newRunningSum, sums)
2. Node Depths
Python
# This is the class of the input binary tree.
class BinaryTree:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
## Iterative Approach using Stack
## O(N) time | O(h) space h=height (depth)
def nodeDepths(root, depth = 0 ):
# Write your code here.
sumOfDepths = 0
stack = [{"node":root, "depth":0}]
while len(stack) > 0:
nodeInfo = stack.pop()
node, depth = nodeInfo["node"], nodeInfo["depth"]
if node is None:
continue
sumOfDepths += depth
stack.append({"node":node.left, "depth": depth +1 })
stack.append({"node":node.right, "depth": depth +1 })
return sumOfDepths
## Recursive Approach
## O(N) time | O(h) space h=height
# def nodeDepths(root, depth = 0 ):
# # Write your code here.
# if root is None:
# return 0
# print(root.value)
#
# return depth + nodeDepths(root.left, depth+1) + nodeDepths(root.right, depth+1)
root = BinaryTree(1)
root.left = BinaryTree(2)
root.left.left = BinaryTree(4)
root.left.left.left = BinaryTree(8)
root.left.left.right = BinaryTree(9)
root.left.right = BinaryTree(5)
root.right = BinaryTree(3)
root.right.left = BinaryTree(6)
root.right.right = BinaryTree(7)
print(nodeDepths(root))
##16
