[[Binary trees and Binary search trees]]

Problem

You are given a binary tree where each node contains a binary digit (0 or 1). Each root-to-leaf path represents a binary number. Compute the sum of all these numbers.

• Example Path: root(1) -> child(0) -> leaf(1) represents binary 101, which is 5.

Brainstorming

The key idea is we need to calculate the partial sum at the node we are processing before we pass it on to the child nodes. that way we are essentially carrying down the results and adding values to it as we go down. This is a pre order traversal ( root -> left -> right) along with the node we would also need to maintain the “sum” as input to the recursive helper as partial sum so far

The sum operation is P * 2 + D where P is the parent sum so far and D is the current node value (it is the « 1 left shit operation )

Below is the algorithm for this

1. define the helper sum_root_to_leaf(node, path_sum_so_far)
2. if the node is none we return 0 to make sure there is no contribution to the sum
3. we calculate the sum at the current node new_sum = path_sum_so_far * 2 + node.data
4. we check if both the right and the left node exists before passing the sum to them
5. next we calculate the left and the right sum ( pre order traversal)
6. finally we return the total of left and right

class BinaryTreeNode:
	def __init__(self, data=None, left=None, right=None):
		self.data = data
		self.left = left
		self.right = right
	

def sum_root_to_leaf(node:BinaryTreeNode, path_sum_so_far):
	# First base case if the node is None
	if node is None:
		return 0
	# calculate the sum at the current node
	new_sum = path_sum_so_far * 2 + node.data
	# Second base case if the left and right child of the node is none
	if node.left is None and node.right is None:
		return new_sum
	left_sum = sum_root_to_leaf(node.left, new_sum)
	right_sum = sum_root_to_lead(node.right, new_sum)
	
	return left_sum + right_sum