Binary Tree Path Sum

DFS using recursion.

def has_path(root, sum):

  # Return is root is False (when child doesn't exist)
  if root is None:
    return False

  # If leaf node and total sum = travesed sum, return True
  if root.val == sum and root.left is None and root.right is None:
    return True

  # Recursively Call function for left, then Right children
  # Pass in Sum - root.val
  return has_path(root.left, sum - root.val) or has_path(root.right, sum - root.val)

All Paths for a Sum

Lie above, we use a recursion for our DFS. But for this one, we don't return True when we get a valid path. Instead, we add the path to the allPaths list. I used a stack to keep track of the current Path. After each node is processed and performs the recusive call on its children, we pop that node's value from the stack.

Time Complexity for this is actually O(n*log(n)). We visit each node which is O(n), and for each leaf, we potentially need to copy the path, which is O(logN) - (this is the maximum number of nodes in a path)

def find_paths(root, sum):
  allPaths = []
  currentPath = deque()
  find_paths_recursive(root, sum, currentPath, allPaths)
  
  return allPaths

def find_paths_recursive(root, requiredSum, currentPath, allPaths):

  if root is None:
    return
  
  currentPath.append(root.val)

  if root.val == requiredSum and root.left is None and root.right is None:
    allPaths.append(list(currentPath))
  else:
    find_paths_recursive(root.left, requiredSum - root.val, currentPath, allPaths)
    find_paths_recursive(root.right, requiredSum - root.val, currentPath, allPaths)
  
  currentPath.pop()

Sum of Path Numbers

Recursive function adds to the path sum. If the node is a leaf, then return the pathSum to that point, else, continue with the left then right child.

def find_sum_of_path_numbers(root):
  
  if root is None:
    return None
  
 
  return find_sum_of_path_numbers_recursive(root, 0)


def find_sum_of_path_numbers_recursive(root, pathSum):

  if root is None:
    return 0

  pathSum = (pathSum * 10) + root.val

  # If this is a leaf node, then return the sum of the path
  if root.left is None and root.right is None:
    return pathSum

  # If not leaf, then call recursively on left and right
  return find_sum_of_path_numbers_recursive(root.left, pathSum) + find_sum_of_path_numbers_recursive(root.right, pathSum)

Path With Given Sequence

Just keep track of index of sequence array

def find_path(root, sequence):
  
  return find_path_recursive(root, sequence, 0)

def find_path_recursive(root, sequence, index):

  if root is None:
    return False

  # If our index is beyond the length of the sequence, or the current node.val
  # Does not match the next number in the sequence
  if root.val != sequence[index] or (index >= len(sequence)):
    return False

  # If leaf node and this node matches the last element of the list
  if root.left is None and root.right is None and (len(sequence) - 1) == index:
    return True
  
  return find_path_recursive(root.left, sequence, index + 1) or find_path_recursive(root.right, sequence, index + 1)

Count Paths for a Sum

Kinda similar to "All Paths for a Sum" above. For this one, we need to check sum paths too (doesn't have to start with root and doesn't have to end with leaf). So, as each node, we add all the subpaths that equal the sum. We use a for loop to iterate backwards starting with the current node, so that we don't count any path twice (we are checking all the paths that end at the current node).

def count_paths(root, S):
  return count_paths_recursive(root, S, [])

def count_paths_recursive(currentNode, S, currentPath):

  if currentNode is None:
    return 0

  # Append current node's value to current path
  currentPath.append(currentNode.val)

  pathCount = 0
  pathSum = 0

  # Find sum of all sub paths ending with current node
  for i in range(len(currentPath) - 1, -1, -1):
    pathSum += currentPath[i]

    if pathSum == S:
      pathCount += 1

  # Recursively call for left and right children
  # Add returned pathCounts
  pathCount += count_paths_recursive(currentNode.left, S, currentPath)
  pathCount += count_paths_recursive(currentNode.right, S, currentPath)

  # Remove this node's value from recursion stack
  del currentPath[-1]

  # Return all paths ending in either this node or any nodes in subtree
  return pathCount

Tree Diameter

This suggested to use a class, so that self.treeDiameter can remain global. This is so it can be updated at each node within the recursive call. We could also pass it in as the first element in a list so that it's passed by reference.

Once the calls get to a leaf node, its children are None and return 0. So the leaf node returns 1. At all nodes on up, the diameter passing through each node is checked (left + right) + 1. And then the maximum child path max(left, right) + 1 is returned to caller.

Rather than the number of edges, this wants us to calculate the number of nodes, which is one greater than the number of edges.

class TreeDiameter:

  def __init__(self):
    self.treeDiameter = 0

  def find_diameter(self, root):
    self.calculate_height(root)
    return self.treeDiameter

  def calculate_height(self, root):
    # If leaf, then 0
    if root is None:
      return 0

    left = self.calculate_height(root.left)
    right = self.calculate_height(root.right)

    self.treeDiameter = max(self.treeDiameter, left + right + 1)

    return max(left, right) + 1

Max Path Sum

Similar to above problem. Except instead of calculating height, we calculate sum. The main difference is if get_max_gain(left) or get_max_gain(right) returns a negative number, then we use 0 in the calculating. Because if the subtree is negative, then there is no reason to use them (terminate at current node).

def find_maximum_path_sum(root):
  max_path = float("-inf")

  def get_max_gain(node):

    nonlocal max_path

    if node is None:
      return 0

    # If left/right subtree is negative, then just make it 0
    # We won't use it if its negative
    max_gain_on_left = max(get_max_gain(node.left), 0)
    max_gain_on_right = max(get_max_gain(node.right), 0)

    # Calculate max Path Sum where this node is the root
    max_as_root = node.val + max_gain_on_right + max_gain_on_left

    # Update global max_path
    max_path = max(max_path, max_as_root)

    # Now we return this node's value, plus left OR right subtree, 
    # depending on which is greater (since we can only use one).
    # This is used for path including this node (but not as the root)
    return node.val + max(max_gain_on_left, max_gain_on_right)

  get_max_gain(root)
  return max_path