https://leetcode.com/problems/sum-of-root-to-leaf-binary-numbers

Let us traverse our tree and change values of nodes, so when we reach leaf we will have in this leaf exactly the number we need to add to total sum. Imagine, we have path 10110, then let us look at sequence: 1, 10, 101, 1011, 10110, which is equivalent to 1, 2, 5, 11, 22.

  1. If we reached leaf, add value of this leaf to total sum.
  2. Check left and right children and if they exist, update their values; run dfs for these children.

Complexity: time complexity is O(n): to traverse our tree. Space complexity is O(h) for dfs stack. Note, that we change our tree in process, but it can be easily avoided: instead of changing values we can return value for dfs function.

class Solution:
    def sumRootToLeaf(self, root):
        def dfs(node):
            if not node.left and not node.right: self.sum += node.val
            for child in filter(None, [node.left, node.right]):
                child.val += node.val * 2
                dfs(child)
          
        self.sum = 0
        dfs(root)
        return self.sum

Solution 2: without changing tree

class Solution:
    def sumRootToLeaf(self, root):
        def dfs(node, Q):
            if not node.left and not node.right: self.sum += Q
            for child in filter(None, [node.left, node.right]):
                dfs(child, Q*2 + child.val)
          
        self.sum = 0
        dfs(root, root.val)
        return self.sum

If you like the solution, you can upvote it on leetcode discussion section: Problem 1022